Conflict-free chromatic guarding of funnels (in the V2P-model)

Eppstein's Conga Line

Graph searching with and without contamination and tree-width

Partitions of discrete boxes

Cops and robbers: Monotonicity in graph searching (edge search and node search)

Über Dicke und Split-Dicke von Graphen

Smoothed analysis of order types (joint work with Ivor van der Hoog and Martijn van Schaik)

Abstract:

Consider an ordered point set P. Its order type, denoted by χ__P, is a map which assigns to every triple of points a value in {+,-,0} based on whether the points are collinear (0), oriented clockwise (-) or counter-clockwise (+). An abstract order type is a map χ from all triples of points to {+,-,0} that satisfies the following condition: for every set of five elements S⊂{1,…,n} its induced order type χ_{_S} is realizable by a point set. Planar point sets are among the most basic and natural geometric objects of study in Discrete and Computational Geometry. Properties of point sets are relevant in theory and practice alike. It is known that deciding if an abstract order type is realizable is complete for the existential theory of the reals. Our results show that order type realizability is much easier for realistic instances than in the worst case. In particular, we can recognize instances in "expected NP-time". This is one of the first ∃R-complete problems analyzed under the lens of Smoothed Analysis.

Using SAT Solvers in Combinatorics and Geometry

Abstract

We discuss how modern SAT solvers such as Minisat or Glucose can be used to tackle mathematical problems. We present some of our recent results on various problems to give the audience a better understanding, which problems might be tackled in this fashion, and which problems might not.

Besides the naive SAT formulation also further ideas might be required to tackle certain problems - additional constraints (such as statements which hold "without loss of generality") might need to be added to the SAT model so that it becomes solvable in reasonable time. In particular, to tackle universal point sets for planar graphs, we present a sophisticated approach which combines the following four powerful tools: complete enumeration of order types, complete enumeration of (planar) graphs, SAT solvers, and IP solvers.

Literature

• K. Däubel, S. Jäger, T. Mütze, and M. Scheucher. On orthogonal symmetric chain decompositions. In Proc. EUROCOMB 2019. Full version to appear in the Electronic Journal of Combinatorics (EJC). [arXiv:1810.09847]
• T. Mütze and M. Scheucher. On L-shaped Point Set Embeddings of Trees: First Non-embeddable Examples. In Proc. Graph Drawing 2018. [arXiv:1807.11043]
• M. Scheucher. On Disjoint Holes in Point Sets. In Proc. EUROCOMB 2019. [arXiv:1807.10848]
• M. Scheucher, H. Schrezenmaier, and R. Steiner. A Note On Universal Point Sets for Planar Graphs. In Proc. Graph Drawing 2019. [arXiv:1811.06482]

Counting Pseudoline Arrangements