# Intersection graphs and geometric objects in the plane

## Hoffmann, Udo

In this thesis, we consider several aspects of representations of graphs in the plane. We consider mainly intersection and visibility representations of graphs. In both kind of representations, the vertices are represented by sets in the plane. Intersection representations represent the edges by the intersection of two sets. In visibility graphs, an edge corresponds to a visibility between the sets. In the first part, we consider connections between representations of bipartite segment intersection graphs and their order dimension. In Chapter 1, we show that the order dimension of grid intersection graphs, the intersection graphs of horizontal and vertical segments, is at most four. We use this observation to study the containment relation of many subclasses of grid intersection graphs. We generalize the observation on the order dimension of grid intersection graphs, by showing that the order dimension of bipartite segment intersection graphs is at most linear in the number of slopes that is used in a representation. This leads to the study of the slope number of segment intersection graphs, the minimal number of slopes that is sufficient to represent an intersection graph. In Chapter 2, we show that the slope number of segment intersection graphs is NP-hard to compute, and that it behaves "non-continuously'', i.e., it may drop, from a linear number in the number of segments down to two, upon the removal of a single vertex. The proofs in the first part are based on combinatorial properties of the graphs. In the second part, we deal with the realizability problem and the complexity class existential theory of the reals (ETR). Many geometric representation problems for graphs are complete in ETR, for example the recognition of segment intersection graphs. We show that computing the slope number of segment intersection graphs (Chapter 4) and the recognition of point visibility graphs (Chapter 5) is complete in ETR. Both proofs are based on the ETR-hardness of the realizability of circular sequences, the order of slopes of lines that are spanned by a point sets, which we present in Chapter 3. We finish in Chapter 6, by showing that determining the minimum number of slopes that is sufficient for a planar straight line drawing of a graph, the planar slope number of a graph, is also complete in ETR. We discuss consequences the ETR-hardness for properties of the representation.
In dieser Arbeit beschÃ¤ftigen wir uns mit verschiedenen Darstellungsarten von Graphen in der Ebene. HauptsÃ¤chlich behandeln wir dabei Schnitt- und Sichtbarkeitsdarstellungen. Bei beiden Darstellungsarten werden die Knoten durch Mengen in der Ebene dargestellt. Bei Schnittgraphen existiert eine Kante zwischen zwei Knoten wenn die zugehÃ¶rigen Mengen sich schneiden. Kanten in Sichtbarkeitsgraphen existieren, wenn Mengen zweier Knoten sich sehen kÃ¶nnen, also eine Verbindungsstrecke zwischen zwei Punkten der Mengen existiert, die nicht von einer anderen Menge geschnitten wird. Im ersten Teil dieser Arbeit untersuchen wir einen Zusammenhang zwischen bipartiten Schnittgraphen von Segmenten und der Ordnungsdimension der zugehÃ¶rigen partiellen Ordnung. In Kapitel 1 zeigen wir, dass die Ordnungsdimension von Gitterschnittgraphen, den Schnittgraphen horizontaler und vertikaler Segmente, hÃ¶chstens vier ist. Wir verwenden diese Beobachtung um das VerhÃ¤ltnis vieler Unterklassen von Gitterschnittgraphen zu bestimmen. Wir verallgemeinern die Beobachtung Ã¼ber die Dimension von Gitterschnittgraphen und zeigen, dass die Ordnungsdimension von bipartiten Segmentschnittgraphen unbegrenzt ist, sie jedoch hÃ¶chstens linear in der Anzahl der Steigungen ist. Dies fÃ¼hrt zu einer Untersuchung der Steigungszahl von Segmentschnittgraphen, der minimalen Anzahl von Steigungen, die fÃ¼r die Darstellung eines Segmentschnittgraphen benÃ¶tigt wird. In Kapitel 2 zeigen wir, dass das Berechnen der Steigungszahl NP-schwer ist. AuÃŸerdem zeigen wir, dass die Steigungszahl sich "unstetig'' verhÃ¤lt: Das Entfernen eines Knoten von einem Graphen mit linearer Steigungszahl kann zu einem Gitterschnittgraphen fÃ¼hren. WÃ¤hrend die Beweise im ersten Teil eher kombinatorisch sind, betrachten wir im zweiten Teil Realisierbarkeitsprobleme und die KomplexitÃ¤tsklasse "existential theory of the reals" (ETR). Viele geometrische Probleme sind ETR-vollstÃ¤ndig, wie zum Beispiel die Erkennung von Segmentschnittgraphen. Wir zeigen, dass die Berechnung der Steigungszahl von Segmentschnittgraphen (Kapitel 4) und die Erkennung von Sichtbarkeitsgraphen von Punktmengen (Kapitel 5) ETR-schwer ist. Beide Beweise basieren auf der ETR-Schwere der Realisierbarkeit von "circular sequences", der Reihenfolge der Steigungen der durch eine Punktmenge aufgespannter Menge von Geraden. Dieser Beweis basiert auf "Mnevs universality theorem" und wird in Kapitel 3 prÃ¤sentiert. Zum Abschluss zeigen wir, dass die Berechnung der minimalen Anzahl von Steigungen in einer planaren, geradlinigen Zeichnung, der planaren Steigunszahl eines planaren Graphen, ETR-schwer ist.