Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Tuesday, February 04, 2020, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Manfred Scheucher (Technische Universität Berlin)

Topological Drawings meet SAT Solvers and Classical Theorems of Convex Geometry

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login