Colloquium by Manfred Scheucher (Techniche Universität Berlin): Topological Drawings meet SAT Solvers and Classical Theorems of Convex Geometry

Nov 25, 2019 | 04:00 PM s.t.

In a simple topological drawing of the complete graph $K_n$, vertices are mapped to points in the plane, edges are mapped to simple curves connecting the corresponding end points, and each pair of edges intersects at most once, either in a common vertex or in a proper crossing.
We discuss an axiomatization of simple drawings and for various sub-classes and present a SAT model. With the aid of modern SAT solvers, we investigate some famous and important classical theorems from Convex Geometry (such as Caratheodory’s, Helly's, Kirchberger's Theorem, and the Erdös-Szekeres Theorem) in the context of simple drawings.

This is joint work with Helena Bergold, Stefan Felsner, Felix Schröder, and Raphael Steiner.

Research is in progress.

Time & Location

Nov 25, 2019 | 04:00 PM s.t.

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
Room 005 (Ground Floor)

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)