Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-5580
Main Title: Intersection graphs and geometric objects in the plane
Translated Title: Schnittgraphen und geometrische Objekte in der Ebene
Author(s): Hoffmann, Udo
Advisor(s): Felsner, Stefan
Referee(s): Felsner, Stefan
Mulzer, Wolfgang
Cardinal, Jean
Granting Institution: Technische Universität Berlin
Type: Doctoral Thesis
Language Code: en
Abstract: 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.
URI: http://depositonce.tu-berlin.de/handle/11303/5993
http://dx.doi.org/10.14279/depositonce-5580
Exam Date: 24-Mar-2016
Issue Date: 2016
Date Available: 21-Nov-2016
DDC Class: DDC::500 Naturwissenschaften und Mathematik::510 Mathematik::510 Mathematik
Subject(s): geometric graphs
intersection graphs
visibility graphs
order types
planar graphs
geometrische Graphen
Schnittgraphen
Sichtbarkeitsgraphen
Punktkonfigurationen
planare Graphen
Creative Commons License: https://creativecommons.org/licenses/by/4.0/
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 2 Mathematik und Naturwissenschaften » Institut für Mathematik » Publications

Files in This Item:
File Description SizeFormat 
hoffmann_udo.pdf1.22 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.