# Convex contact representations of planar graphs

## Schrezenmaier, Hendrik

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.