Geometric Representations of Graphs with Low Polygonal Complexity
| dc.contributor.advisor | Felsner, Stefan | en |
| dc.contributor.author | Ueckerdt, Torsten | en |
| dc.contributor.grantor | Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften | en |
| dc.date.accepted | 2011-11-04 | |
| dc.date.accessioned | 2015-11-20T21:17:01Z | |
| dc.date.available | 2012-04-25T12:00:00Z | |
| dc.date.issued | 2012-04-25 | |
| dc.date.submitted | 2012-04-25 | |
| dc.description.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. | de |
| dc.description.abstract | 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. | en |
| dc.identifier.uri | urn:nbn:de:kobv:83-opus-35093 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/3487 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-3190 | |
| dc.language | English | en |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | Graphentheorie | de |
| dc.subject.other | Graphs | en |
| dc.subject.other | Intersection | en |
| dc.subject.other | Planarity | en |
| dc.subject.other | Polygons | en |
| dc.title | Geometric Representations of Graphs with Low Polygonal Complexity | en |
| dc.title.translated | Geometrische Repräsentationen von Graphen mit geringer polygonaler Komplexität | de |
| dc.type | Doctoral Thesis | en |
| dc.type.version | publishedVersion | en |
| tub.accessrights.dnb | free | * |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.identifier.opus3 | 3509 | |
| tub.identifier.opus4 | 3306 | |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
Files
Original bundle
1 - 1 of 1