30.01.2012

Informatik-Kolloquium

Im Wintersemester 2011/2012 findet im Rahmen des Informatik-Kolloquiums der folgende Vortrag statt:

Montag, 30. Januar 2012, 17:00 Uhr, Turing-Hörsaal

Prof. Dr. André Schulz (Universität Münster)

Algorithms for Realizing 3d Polytopes

Polytopes are fundamental objects in combinatorial and linear optimization und convex geometry. Every polytope is equipped with a combinatorial structure that decodes how vertices, edges, andhigher-dimensional facets are related to each other. The question arises which combinatorial descriptions can be geometrically realized as polytopes. Although this question is considerably hard, by Steinitz' seminal 1918 theorem the situation in 3d is well understood. In particular, the combinatorial structure for 3d polytopes is completely determined by the polytope graph, and the graphs of 3d polytopes are exactly the planar 3-connected graphs.

In this talk, I will discuss algorithmic aspects of embedding a planar 3-connected graph as a 3d polytope. The construction goes back to a technique discovered by James Clark Maxwell in the 19th century. As a result, we obtain a realization that can be embedded on the integer grid and requires only a linear number of bits per vertex. In order to bound the size of the coordinate representation, we have to bound the number of spanning trees that a planar graph can have. In the end of thetalk, I will give an overview on recent related results and open problems.