André Schulz

Lifting Planar Graphs to Realize Integral 3-Polytopes and Topics in Pseudo-Triangulations

Betreuer: Prof. Dr. Günter Rote
Abschluss: PhD
Abgabedatum: 05.06.2008
Homepage des Autors:

Kurzbeschreibung

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.

Downloads