Convex contact representations of planar graphs

Schrezenmaier, Hendrik

FG Diskrete Mathematik

The goal of this dissertation is to study contact representations of plane graphs with convex shapes in the plane, with a special focus on convex polygons. The classical Circle Packing Theorem by Koebe from 1936 states that each plane graph has a contact representation with disks, i.e., the vertices of the graph are represented by interiorly disjoint disks in the plane such that the edges of the graph correspond to touching disks. A remarkable generalization of this theorem is the Convex Packing Theorem by Schramm. It states that, if we prescribe an individual compact convex prototype for each vertex of a plane graph, there exists a contact representation of this graph in which each vertex is represented by a scaled copy of its prototype. In the case that the prototypes do not have smooth boundaries, the only known proof of this theorem is based on the Brouwer fixed point theorem and does not seem to give any insights into questions like those for the uniqueness or the complexity of the computation of the contact representations. In this dissertation we study contact representations of plane graphs with so called similarly-aligned odd K-gons and parallel-sided even K-gons for a fixed K. These classes of polygons generalize equiangular and therefore also regular K-gons for odd and even K, respectively. We describe the combinatorial structure of these contact representations by integral flows of planar graphs with prescribed excesses at the vertices, known as !-flows. In particular, we obtain a lattice structure on the set of all possible contact structures of a graph. This lattice structure plays a role in an algorithm that is supposed to compute a contact representation of a given graph with individually prescribed similarly-aligned odd K-gons or parallel-sided even K-gons as prototypes for the vertices. Based on a contact structure, the algorithm builds a system of linear equations and solves it. If the solution is non-negative, it encodes the wanted contact representation. In this case the representation is constructed and the algorithm terminates. Otherwise negative variables guide a change of the contact structure and the procedure is restarted with the new contact structure. Similar algorithms have been proposed for contact representations with homothetic triangles and squares. We cannot prove that this procedure terminates. But using the ideas of this approach, we can still prove the existence of the wanted contact representation. With a convergence argument we can then reprove the existence of contact representations of plane graphs with arbitrary individually prescribed compact convex prototypes for the vertices.
In dieser Arbeit beschäftigen wir uns mit Kontaktdarstellungen planarer Graphen mit konvexen Formen in der Ebene, mit besonderem Fokus auf konvexe Polygone. Ein klassisches Resultat auf diesem Gebiet ist das Kreispackungstheorem von Koebe von 1936, das besagt, dass jeder planare Graph eine Kontaktdarstellung mit Kreisscheiben besitzt, d. h., die Knoten des Graphen werden als Kreisscheiben in der Ebene mit paarweise disjunktem Inneren dargestellt, so dass die Kanten des Graphen den Paaren sich berührender Kreisscheiben entsprechen. Eine bemerkenswerte Verallgemeinerung dieses Theorems ist das Konvexpackungstheorem von Schramm. Dieses besagt, dass, wenn wir für jeden Knoten eines planaren Graphen einen individuellen kompakten konvexen Prototyp vorschreiben, dieser Graph eine Kontaktdarstellung besitzt, in der jeder Knoten durch eine skalierte Kopie seines Prototyps dargestellt wird. Wenn die Ränder der Prototypen nicht glatt sind, beruht der einzige bekannte Beweis dieses Theorems auf dem Fixpunktsatz von Brouwer und scheint keine Erkenntnisse zu liefern, die bei der Beantwortung von Fragen nach der Eindeutigkeit oder der Komplexität der Berechnung der Kontaktdarstellungen helfen. In dieser Dissertation untersuchen wir Kontaktdarstellungen planarer Graphen mit so genannten ähnlich ausgerichteten ungeraden K-Ecken und parallelseitigen geraden K-Ecken für ein festes K. Diese Klassen von Polygonen sind Verallgemeinerungen von gleichwinkligen und damit insbesondere regulären K-Ecken für ungerade beziehungsweise gerade K. Wir beschreiben die kombinatorische Struktur dieser Kontaktdarstellungen als ganzzahlige Flüsse von planaren Graphen mit vorgeschriebenen Überschüssen an den Knoten, so genannte !-Flüsse. Insbesondere erhalten wir eine Verbandsstruktur auf der Menge aller möglichen Kontaktstrukturen eines Graphen. Diese Verbandsstruktur spielt eine Rolle in einem Algorithmus, der eine Kontaktdarstellung eines gegebenen Graphen mit individuell vorgegebenen ähnlich ausgerichteten ungeraden K-Ecken oder parallelseitigen geraden K-Ecken als Prototypen für die Knoten berechnen soll. Basierend auf einer Kontaktstruktur stellt der Algorithmus ein lineares Gleichungssystem auf und löst es. Wenn die Lösung nichtnegativ ist, kodiert sie die gesuchte Kontaktdarstellung. In diesem Fall kann die Kontaktdarstellung konstruiert werden und der Algorithmus terminiert. Andernfalls geben die negativen Variablen einen Hinweis, wie die Kontaktstruktur geändert werden kann, und die Prozedur wird mit der neuen Kontaktstruktur neu gestartet. Ähnliche Algorithmen sind bereits für die Berechnung von Kontaktdarstellungen mit homothetischen Dreiecken und Quadraten vorgeschlagen worden. Wir können nicht beweisen, dass der Algorithmus terminiert. Allerdings können wir die Ideen dieses Algorithmus verwenden, um die Existenz der gesuchten Kontaktdarstellungen zu beweisen. Mit Hilfe eines Konvergenzarguments erhalten wir schließlich einen neuen Beweis für die Existenz von Kontaktdarstellungen planarer Graphen mit beliebigen individuell vorgeschriebenen kompakten konvexen Prototypen für die Knoten.