Schematics of Graphs and Hypergraphs

DSpace Repository

Show simple item record

dc.contributor.advisor Kaufmann, Michael (Prof. Dr.)
dc.contributor.author Bruckdorfer, Till Martin
dc.date.accessioned 2016-01-12T08:10:56Z
dc.date.available 2016-01-12T08:10:56Z
dc.date.issued 2016
dc.identifier.other 454021127 de_DE
dc.identifier.uri http://hdl.handle.net/10900/67484
dc.identifier.uri http://nbn-resolving.de/urn:nbn:de:bsz:21-dspace-674846 de_DE
dc.identifier.uri http://dx.doi.org/10.15496/publikation-8904
dc.description.abstract Graphenzeichnen als ein Teilgebiet der Informatik befasst sich mit dem Ziel Graphen oder deren Verallgemeinerung Hypergraphen geometrisch zu realisieren. Beschränkt man sich dabei auf visuelles Hervorheben von wesentlichen Informationen in Zeichenmodellen, spricht man von Schemata. Hauptinstrumente sind Konstruktionsalgorithmen und Charakterisierungen von Graphenklassen, die für die Konstruktion geeignet sind. In dieser Arbeit werden Schemata für Graphen und Hypergraphen formalisiert und mit den genannten Instrumenten untersucht. In der Dissertation wird zunächst das „partial edge drawing“ (kurz: PED) Modell für Graphen (bezüglich gradliniger Zeichnung) untersucht. Dabei wird um Kreuzungen im Zentrum der Kante visuell zu eliminieren jede Kante durch ein kreuzungsfreies Teilstück (= Stummel) am Start- und am Zielknoten ersetzt. Als Standard hat sich eine PED-Variante etabliert, in der das Längenverhältnis zwischen Stummel und Kante genau 1⁄4 ist (kurz: 1⁄4-SHPED). Für 1⁄4-SHPEDs werden Konstruktionsalgorithmen, Klassifizierung, Implementierung und Evaluation präsentiert. Außerdem werden PED-Varianten mit festen Knotenpositionen und auf Basis orthogonaler Zeichnungen erforscht. Danach wird das BUS Modell für Hypergraphen untersucht, in welchem Hyperkanten durch fette horizontale oder vertikale – als BUS bezeichnete – Segmente repräsentiert werden. Dazu wird eine vollständige Charakterisierung von planaren Inzidenzgraphen von Hypergraphen angegeben, die eine planare Zeichnung im BUS Modell besitzen, und diverse planare BUS-Varianten mit festen Knotenpositionen werden diskutiert. Zum Schluss wird erstmals eine Punktmenge von subquadratischer Größe angegeben, die eine planare Einbettung (Knoten werden auf Punkte abgebildet) von 2-außenplanaren Graphen ermöglicht. de_DE
dc.language.iso en de_DE
dc.publisher Universität Tübingen de_DE
dc.rights ubt-podok de_DE
dc.rights.uri http://tobias-lib.uni-tuebingen.de/doku/lic_mit_pod.php?la=de de_DE
dc.rights.uri http://tobias-lib.uni-tuebingen.de/doku/lic_mit_pod.php?la=en en
dc.subject.classification Graphenzeichnen , Hypergraph de_DE
dc.subject.ddc 004 de_DE
dc.subject.other Graph Drawing en
dc.subject.other Planarity en
dc.subject.other Graphs en
dc.subject.other Hypergraphs en
dc.title Schematics of Graphs and Hypergraphs en
dc.type PhDThesis de_DE
dcterms.dateAccepted 2015-12-17
utue.publikation.fachbereich Informatik de_DE
utue.publikation.fakultaet 7 Mathematisch-Naturwissenschaftliche Fakultät de_DE
utue.publikation.fakultaet 7 Mathematisch-Naturwissenschaftliche Fakultät de_DE

Dateien:

This item appears in the following Collection(s)

Show simple item record