Lifting planar graphs to realize integral 3-polytopes and topics in pseudo- triangulations

Abstract

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.

Das Heben von planaren Einbettungen mit Gleichgewichtsstress ist eine Methode, die bereits im 19. Jahrhundert Anwendung fand. Wir stellen diese Methode vor und erstellen Werkzeuge, welche es erlauben, das Heben von planaren Einbettungen effektiv auszuführen. In der Dissertation werden wir die Technik zum Heben planarer Graphen auf geometrische Problemstellungen anwenden. Als erste Anwendung zeigen wir, wie man 3-Polytope mit kleinen ganzzahligen Koordinaten einbetten kann. Die vorgestellte Methode verbessert die bisherige obere Schranke für die größte Koordinate von O(2^{18n^2}) auf O(2^{7.55n}). Eine neue, verallgemeinerte Variante der Tutte-Einbettung stellt sicher, dass die planare 2d-Einbettung einen Gleichgewichtsstress besitzt und deshalb hochhebbar ist. Wir zeigen Zusammenhänge zwischen der Größe der Einbettung und der maximalen Anzahl von Spannbäumen auf planaren Graphen auf. Das zweite Anwendungsgebiet für das Heben planarer Graphen sind Fragestellungen über Pseudo-Triangulierungen. Unser Hauptresultat zeigt, wie man reguläre Triangulierungen als lineares Programm über dem Polytop der gespitzten Pseudo- Triangulierungen modellieren kann. Wir führen eine Entsprechung der Delaunay Triangulierung für gespitzte Pseudo-Triangulierungen von einfachen Polygonen ein. Unser Ansatz basiert auf der Parabolid-Abbildung, sowie auf Verallgemeinerungen von linearen Programmen, welche die Delaunay- Triangulierung für spezielle Szenarien berechnen. Des Weiteren untersuchen wir die kanonische Pseudo-Triangulierung und diskutieren einige ihrer geometrischen Eigenschaften. Unsere Erkenntnisse führen zur Charakterisierung von gespitzten Pseudo-Triangulierungen als minimal starre Graphen, welche eine gegebene Last mit positiven inneren Kantengewichten ausgleichen können. Die Dissertation enthält außerdem Resultate über Pseudo-Triangulierungen, welche nicht von der Hebe-Technik Gebrauch machen. Wir zeigen, dass eine Sequenz von super-polynomiell viele Konvexitäts-erzeugende Flips existiert, die eine polyedrische Pseudo-Triangulierung in eine lokal konvexe Oberfläche zu überführt. Dies wird erreicht, in dem wir ein einfaches Polygon konstruieren, welches zwei gespitzte Pseudo-Triangulierungen besitzt, zwischen denen eine verbessernde Flipsequenz der Länge n^{\Theta(\log n)} existiert. Des Weiteren zeigen wir, dass es erstens NP-schwer ist zu entscheiden, ob ein geometrischer Graph eine Pseudo-Triangulierung enthält und zweitens, dass es ebenfalls NP- schwer ist zu entscheiden, ob sich ein geometrischer Graph zu einer Pseudo- Triangulierung mit kleinem Knotengrad erweitern lässt. Beide Probleme werden in verschiedenen Varianten untersucht. In diesem Zusammenhang erhalten wir auch einen neuen, vereinfachten Beweis der NP-Vollständigkeit des Triangulierungs-Existenz Problems.