Monday, April 18, 2011
Freie Universität Berlin
Institut für Informatik
Takustrasse 9
14195 Berlin
room MA 005
Lecture - 14:15
Abstract:
Due to Steinitz seminal 1916 theorem the graphs that admit a realization as 3D convex polytope are the planar 3-connected graphs. Although Steinitz' proof is constructive, the obtained embeddings have undesirable properties. In particular, one might need
exponentially many bits to represent the coordinates of the induced representation.
In the 19th century James C. Maxwell described a bijection between the projections of 3D polytopes and 2D geometric graphs that fulfill an equilibrium condition. Using this so-called Maxwell-Cremona correspondence it is possible to give an alternative proof of Steinitz theorem by first computing a plane embedding of the graph and then lift the 2D embedding to 3D. I will show how this approach (in conjunction with Tutte's barycentric embeddings) can be used to compute realizations on an integer grid, whose largest coordinate is bounded by $O(147^n)$, $n$ being the number of the vertices of the polytope. For the computation of the actual bound one needs an estimation on the number of spanning trees a planar graph can have. I will briefly discuss how to bound this quantity with help of probabilistic methods.
The embedding algorithm can be modified such that it yields a (non-grid) embedding in which every two vertices have distance at least 1, but the whole embedding fits inside a small box of dimension 2(n - 2) x 2 x 1. I conclude the talk with a linear time algorithm that realizes stacked 3D polytopes (formed by repeatedly stacking a tetrahedron onto a triangular face) on an integer grid of size $O(n^4) x O(n^4) x O(n^{18})$.
Colloquium - 16:00
Abstract: