Lifting planar graphs to realize integral 3-polytopes and topics in pseudo- triangulations
André Schulz · Universitätsbibliothek der FU Berlin Hochschulschriftenstelle u. Dokumentenserver · 2008
Lifting planar embeddings with equilibrium stress is a well known method that dates back to the 19th century. We discuss the known theory about liftings and develop a framework that allows us to apply the lifting technique easily. In this thesis we apply the lifting method to different geometric problems. As a first application we show how to embed 3-polytopes with small integer coordinates. Our method improves the upper bound for the size of the largest coordinate from O(2^{18n^2}) to O(2^{7.55n}). A new generalized version of Tutte's spring embedding assures that a planar 2d-embedding contains an equilibrium stress and is therefore liftable. We point out connections between the size of the integral embedding and the number of maximal spanning forests a planar graph can have. The second field of applications for the lifting technique are topics about pseudo-triangulations. Our main observation shows how to model regular triangulations as linear programs over the polytope of pointed pseudo-triangulations. We introduce an equivalent of the Delaunay triangulation for pointed pseudo-triangulations of simple polygons. Our approach is motivated by the paraboloid lifting of the Delaunay triangulation and the generalization of linear programs that compute the Delaunay triangulation in special cases. We also investigate the so-called canonical pointed pseudo-triangulation and study some of its geometric properties. Our observations lead to a new characterization of pointed pseudo-triangulations as embeddings of minimal rigid graphs that can balance a given load with positive edge weights. The thesis contains also results on pseudo- triangulation problems that were not obtained with help of liftings. We show that a sequence of super-polynomial many convexifying flips exists that transform a lifted pseudo-triangulation into a maximal locally convex surface. This is obtained by constructing a simple polygon that realizes an improving flip sequence of length n^{\Theta(\log n)} between two of its pointed pseudo- triangulation. Furthermore we show that (1) it is NP-hard to decide if a graph contains a pseudo-triangulation and (2) it is NP-hard to decide if a graph can be extended to a pseudo-triangulation with small vertex degree. Both decision problems are studied in different incarnations. We obtain a new and easier NP- completeness proof of the triangulation existence problem, one of the classic NP-complete triangulation problems.