Klassisch werden Graphen durch Zeichnungen in der Ebene repräsentiert, das heißt die Knoten sind Punkte in der Ebene und die Kanten sind Linien, die adjazente Knoten verbinden. Eine Alternative ist, Knoten durch geometrische Objekte der Ebene wie Linien oder Kreise zu repräsentieren, welche sich genau dann schneiden, wenn die korrespondierenden Knoten adjazent sind. In diesem Fall sprechen wir von Schnitt-Repräsentationen. Wenn sich die geometrischen Objekte nur berühren, sprechen wir von Kontakt-Repräsentationen. Eine Straight-Line Triangle Representation (SLTR) ist eine klassische Zeichnung, bei der die Linien Segmente sind und jede Facette ein Dreieck ist. In dieser Arbeit untersuchen wir, welche planaren Graphen ein SLTR besitzen. Wir geben dazu zwei Charakterisierungen an, wobei offen ist, ob sich die ergebenen Bedingungen effizient testen lassen. Mit Hilfe der ersten Charakterisierung können wir einen Satz von de Fraysseix und Ossona de Mendez auf eine neue Weise und einfacher beweisen. Auch geben wir einen einfacheren Beweis eines Theorems von Gonçalves, Lévêque and Pinlou. Die zweite Charakterisierung lässt sich mit einem 2-Güterflussproblem formulieren. Leider ist bekannt, dass das Lösen von 2-Güterflussproblemen NP-schwer ist. Im Positiven haben wir bewiesen, dass SLTRs mit Henneberg-Typ-II-Schritten erweitert werden können. Ein Graph mit n Knoten ist eine generische Schaltung, falls er 2n − 2 Kanten besitzt und jeder Subgraph mit m Knoten höchstens 2m−3 Kanten hat. Es ist bekannt, dass jede generische Schaltung mit Henneberg-Typ-II-Schritten konstruiert werden kann. Daraus folgt, dass jede planare generische Schaltung ein SLTR besitzt. Eng verwandt mit SLTRs sind Dreieck-Kontaktdarstellungen, dass heißt jeder Knoten wird durch ein Dreieck repräsentiert und zwei Dreiecke haben Seitenkontakt genau dann, wenn die Knoten verbunden sind. Dabei darf es keine Lücken in der Repräsentation geben. Wir geben eine Charakterisierung von zweifach zusammenhängenden außerplanaren Graphen, die eine solche Repräsentation in einem konvexen Vieleck haben. Die Bedingungen der Charakterisierung können einfach getestet werden. Zweitens haben wir bewiesen, dass jeder Halin-Graph eine Kontakt-Repräsentation mit Dreiecken in einem Dreieck besitzt. Danach betrachten wir eine Repräsentationsart, bei der die Knoten durch achsenparallele Gitter-Pfade repräsentiert werden. Zwei Knoten sind genau dann adjazent, wenn der Gitter-Pfad des einen Knoten orthogonal auf dem Gitter-Pfad des anderen Knoten endet. Es ist einfach zu charakterisieren, welche Graphen so repräsentiert werden können: Es handelt sich um genau jene Graphen, bei denen jeder Subgraph höchstens zweimal soviel Kanten wie Knoten hat. Diese Graphen werden (2,0)-karg genannt. Wir geben eine Methode an, mit der die Anzahl der Knicke der Gitter-Pfade minimiert werden kann. Das Minimum wird durch Reduktion auf ein Flussproblem berechnet. Damit konnten wir für einige Graphenklassen, die Subklassen von (2,0)-kargen Graphen sind, obere Schranken für die Knickanzahl beweisen.
This thesis is about representations of planar graphs. The vertices of a graph can be represented by points in the plane, two points are connected by a line segment if and only if the two vertices are adjacent. This is called a classical drawing of a graph. Another way of representing graphs is as the contact or intersection representation of geometric objects. One famous example of contact representations is the circle contact representation. In this representation each vertex is represented by a circle in the plane, the circles are internally disjoint and two circles touch if and only if the vertices are adjacent. In this work we consider both a classical drawing with some restrictions as well as two types of contact representations. In Chapter 2 we consider a drawing in the classical setting, i.e. vertices are points in the plane and edges are straight-lines between two points. We ask which graphs admit a straight-line drawing such that all the faces are triangles, this is denoted by Straight-Line Triangle Representation. To the best of our knowledge, it is still open whether, given a planar graph G, the question "Does G admit a straight-line triangle representation?" belongs to P. We will give two characterizations of graphs that admit a straight-line triangle representation. However, we are not aware of an efficient way to check whether a given graph satisfies the conditions. On the positive side, we identify several classes of graphs for which all graphs admit a straight-line triangle representation. In Chapter 3 the question is considered in its dual form: we now ask for a representation in which the vertices are triangles and the edges are side-contacts between two triangles. Such a representation is called a Touching Triangle Representation. We have been able to characterize the biconnected outerplanar graphs that admit a touching triangle representation in a convex polygon. Secondly, we show that every Halin graph admits a touching triangle representation in a triangle. In Chapter 4 the objects that represent vertices are grid-paths and we study contact representations of paths in a grid. The class of graphs that admit a grid-path contact representation is precisely the class of planar (2,0)-sparse graphs. We will give a combinatorial characterization of grid-path contact representations. The interesting question about this representation is whether we can minimize the number of bends, locally as well as globally. Using the combinatorial characterization, we give bounds on the number of bends per vertex, that suffice to represent (2,l)-tight planar graphs for different values of l. In Chapter 5 we will give the current status of the problems addressed in this thesis and the open problems that we have encountered along the way.
