# André Schulz:

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

### 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.