Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-3190
Main Title: Geometric Representations of Graphs with Low Polygonal Complexity
Translated Title: Geometrische Repräsentationen von Graphen mit geringer polygonaler Komplexität
Author(s): Ueckerdt, Torsten
Advisor(s): Felsner, Stefan
Granting Institution: Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Diese Arbeit befasst sich mit der Darstellung eines Graphen als Durchschnittsgraphen in der Ebene. Wir betrachten zwei Varianten einer solchen Darstellung: In der ersten Variante, den side contact representations, werden Knoten durch einfache Polygone repräsentiert, deren Innere disjunkt sind. Jede Kante des Graphen entspricht einer Überschneidung der Ränder der entsprechenden Polygone mit echt positiver Länge, einem sogenannten side contact. In der zweiten Variante, den EPG representations, sind Knoten durch Pfade im ebenen Quadratgitter repräsentiert, und Kanten durch Pfade die mindestens eine Gitterkante gemeinsam haben. In beiden Fällen wird die schlimmstenfalls benötigte polygonale Komplexität der Polygone bzw. Gitterpfade untersucht.
In this thesis we investigate graphs that are represented as intersection graphs in the plane. We consider two types of intersection graphs: In a side contact representation vertices are represented by simple polygons whose interiors are pairwise disjoint. Every edge corresponds to a non-trivial overlap of the boundaries of the corresponding polygons, a so-called side contact. Secondly we consider EPG representations in which vertices are represented by paths in the plane square grid and edges correspond to pairs of paths that have at least one grid edge in common. In both cases we investigate the worst-case polygonal complexity of the polygons, respectively paths, in the representation.
URI: urn:nbn:de:kobv:83-opus-35093
http://depositonce.tu-berlin.de/handle/11303/3487
http://dx.doi.org/10.14279/depositonce-3190
Exam Date: 4-Nov-2011
Issue Date: 25-Apr-2012
Date Available: 25-Apr-2012
DDC Class: 510 Mathematik
Subject(s): Graphentheorie
Graphs
Intersection
Planarity
Polygons
Usage rights: Terms of German Copyright Law
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 
Dokument_6.pdf1.63 MBAdobe PDFThumbnail
View/Open


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