On subclasses of grid intersection graphs

dc.contributor.advisorFelsner, Stefanen
dc.contributor.authorMustata, Irinaen
dc.contributor.grantorTechnische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaftenen
dc.contributor.refereeKöhler, Ekkeharden
dc.date.accepted2014-07-18
dc.date.accessioned2015-11-20T23:49:37Z
dc.date.available2014-10-15T12:00:00Z
dc.date.issued2014-10-15
dc.date.submitted2014-09-25
dc.description.abstractGrid 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.de
dc.description.abstractIn 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.en
dc.identifier.uriurn:nbn:de:kobv:83-opus4-57164
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/4499
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-4202
dc.languageEnglishen
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc500 Naturwissenschaften und Mathematiken
dc.subject.otherGitterde
dc.subject.otherorthogonale Strahlende
dc.subject.otherSchnittgraphende
dc.subject.otherOrthogonal ray treesen
dc.subject.othergrid intersection graphsen
dc.subject.otherorthogonal ray graphsen
dc.subject.otherorthogonal ray treesen
dc.subject.otherunit griden
dc.titleOn subclasses of grid intersection graphsen
dc.title.translatedUnterklassen von Gitterschnittgraphende
dc.typeDoctoral Thesisen
dc.type.versionpublishedVersionen
tub.accessrights.dnbfree*
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.identifier.opus45716
tub.publisher.universityorinstitutionTechnische Universität Berlinen

Files

Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
mustata_irina.pdf
Size:
2.26 MB
Format:
Adobe Portable Document Format

Collections