Felsner, StefanMustata, Irina2015-11-202014-10-152014-10-152014-09-25urn:nbn:de:kobv:83-opus4-57164https://depositonce.tu-berlin.de/handle/11303/4499http://dx.doi.org/10.14279/depositonce-4202Grid intersection graphs (Gitterschnittgraphen, GIGs) sind bipartite Schnittgraphen von orthogonalen Segmenten (waagerecht und senkrecht) in der Ebene. Sie stellen eine viel erforschte Graphenklasse dar, mit vielfältigen Zusammenhängen. Diese Klasse kann dadurch eingeschränkt werden, indem ein Teil (oder beide) der Partition sich durch Segmente von Einheitslänge (unit grid, UGIG), bi- oder monodirektionelle Strahlen zeichnen lässt (orthogonal ray graphs, ORG). Die Kapitel der Doktorarbeit sind unterschiedlichen Themen bezüglich den Unterklassen der GIGs gewidmet: 1. Dieses Kapitel erwähnt vorerst Basisbegriffe die später benutzt werden sollen. Dann stellen wir dem Leser Gamma vor, d.h. die Sammlung der betrachteten Graphenklassen, nach Inklusion geordnet. Auch kommt hier eine Beschreibung von manchen dieser Graphenklassen (GIG, ORG, ray-segment) bezüglich Adjazenz Matrizen. Ein paar neue Ergebnisse der Literatur sind auch erwähnt. 2. Hier zeigen wir, dass die triviale Inklusion zwischen den Graphen Klassen von Gamma vollständig die Beziehungen zwischen den obengenannten Klassen beschreibt. Dies erfolgt durch ausgedachte Gegenbeispiele. Danach betrachten wir die Schnittgraphen von Einheitsquadraten (als BipUSqIG) bezeichnet und zeigen dass diese eine Unterklasse von UGIGs sind und gleichzeitig eine Oberklasse der partiellen Gittergraphen. 3. In diesem Kapitel beweisen wir dass die Erkennung von UGIGs NP-vollständig ist. Auch machen wir ein paar Bemerkungen bezüglich der optimalen Darstellung der UGIGs in der Ebene. 4. Hier wird gezeigt dass, auch wenn für 3-direktionelle ORGs (3-DORGs) die Erkennungskomplexität noch nicht bekannt ist, man ein polynomielles Erkennungsverfahren erfassen kann. Auch zeigen wir, dass alle 3-DORGs ohne Kreise der Länge größer als 4 sich als 2-DORGs darstellen lassen. 5. In diesem Kapitel beschreiben wir alle Bäume und Kreise der Graphenklassen in Gamma. Die Ergebnisse für die 4-DORG und unit-ray Graphen erweisen sich als eng mit den schon bekannten Tatsachen über die 2-DORG Bäume verbunden. 6. Hier untersuchen wir die planare 2-DORGs. Wir zeigen, dass die außerplanare 2-DORGs genau die induzierte Untergraphen von einer besonderen Klasse von Graphen sind. 7. Dieses Kapitel ist eine Zusammenfassung der bisherigen Arbeit und stellt alte und neue Fragen auf dieses Thema bezogen.In their most general form, graphs are abstract structures that admit entirely set-theoretical descriptions. However, one can naturally define graph classes in terms of other mathematical objects, such as geometric ones. A particularly well researched family of graphs is the class of intersection graphs of subsets of the plane. Throughout this thesis, we restrict our attention to the case where the subsets in question are horizontal or vertical segments. A well investigated class of this kind is that of grid intersection graphs. It consists of the bipartite graphs for which one set of the bipartition can be represented by horizontal and the other by vertical segments, such that adjacency is equivalent to the intersection of the corresponding segments. These graphs can be further restricted, e.g. by only permitting unit length segments in one (or both) partitions, or by requiring that the vertices can be represented by horizontal or vertical half-lines. Many interesting questions arise when considering the resulting graph classes: recognition, characterization, relationships between classes, description of the included trees or planar graphs. We aim to tackle several of these questions throughout this thesis. Among our most relevant results is showing that the recognition of unit grid intersection graphs is NP-complete, as well as characterizing the orthogonal ray trees.en500 Naturwissenschaften und MathematikGitterorthogonale StrahlenSchnittgraphenOrthogonal ray treesgrid intersection graphsorthogonal ray graphsorthogonal ray treesunit gridDoctoral Thesis