Combinatorial Concepts and Algorithms for Drawing Planar Graphs
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
Internationale Patentnummer
Link zur Lizenz
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Sammlungen
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
Zusammenfassung
In this thesis, we consider properties of triconnected, planar graphs and devote ourselves to the concepts canonical ordering and Schnyder woods. Whereas these concepts mostly have been investigated separately so far, we focus this thesis on their similarities and connection points, and present them consistently for the first time.
The title "Combinatorial Concepts and Algorithms for Drawing Planar Graphs" already reflects the twofold structure of this thesis.
In Part I "Concepts" we introduce, after giving a summary of fundamental properties of planar graphs, the combinatorial concepts of canonical ordering and Schnyder woods. Furthermore, we reveal their connection to triangle contact representations.
Canonical ordering and Schnyder woods have manifold applications in graph encoding, in dimension theory, in the area of counting various kinds of planar maps, and more.
We concentrate on graph drawing, in particular on triangle contact representations, and present in Part II "Algorithms" appropriate detailed and consistent algorithms with focus on the implementation of the leftist canonical ordering.
Main contributions of this thesis are the introduction of the concept of leftist canonical ordering, the establishing of a connection via ordered path partitions to minimal Schnyder woods, and the provision of efficient algorithms with detailed pseudocodes that ease coding.
Based on these, we show how and on which graph classes these methods can be used to determine homothetic triangle contact representations. Furthermore, we give an extensive overview of related concepts in a consistent manner and provide various new, simpler or more consistent proofs and algorithms.
Zusammenfassung in einer weiteren Sprache
In dieser Arbeit betrachten wir Eigenschaften dreifachzusammenhängender, planarer Graphen und widmen uns insbesondere den beiden Konzepten kanonische Ordnung und Schnyder-Wälder.
Während diese bisher meist getrennt betrachtet wurden, legen wir den Fokus auf ihre Gemeinsamkeiten und stellen die Zusammenhänge zwischen ihnen erstmals auf einheitliche Art und Weise vor.
Der Titel "Kombinatorische Konzepte und Algorithmen zum Zeichnen planarer Graphen" spiegelt bereits die zweigeteilte Grundstruktur dieser Arbeit wider.
In Teil I "Konzepte" führen wir, nach einer Zusammenfassung wesentlicher Eigenschaften planarer Graphen, die kombinatorischen Konzepte kanonische Ordnung und Schnyder-Wälder ein.
Weiterhin zeigen wir den Zusammenhang zwischen ihnen und Kontaktrepräsentationen durch Dreiecke auf.
Von den vielfältigen Anwendungsmöglichkeiten konzentrieren wir uns auf das Zeichnen von Graphen, insbesondere auf Dreiecksrepräsentationen, und stellen in Teil II "Algorithmen" detaillierte und einheitliche Algorithmen dazu vor, wobei ein Schwerpunkt auf der Implementierung der linkesten kanonischen Ordnung liegt.
Die Hauptbeiträge dieser Arbeit sind zum Einen die Einführung des Konzepts der linkesten kanonischen Ordnung und die Herstellung einer Beziehung über geordnete Pfadpartitionen zu minimalen Schnyder-Wäldern, zum Anderen die Bereitstellung von effizienten Algorithmen mit detaillierten, leicht umsetzbaren Pseudocodes.
Aufbauend darauf zeigen wir, wie und auf welchen Graphenklassen diese Verfahren Kontaktrepräsentationen mittels homothetischer Dreiecke ermöglichen.
Darüber hinaus geben wir auf einheitliche Art und Weise eine umfangreiche Übersicht über verwandte Konzepte und stellen zu diesen teilweise neue, einfachere oder besser aufeinander aufbauende Beweise und Algorithmen vor.
Fachgebiet (DDC)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
BAUR, Melanie, 2012. Combinatorial Concepts and Algorithms for Drawing Planar Graphs [Dissertation]. Konstanz: University of KonstanzBibTex
@phdthesis{Baur2012Combi-20228,
year={2012},
title={Combinatorial Concepts and Algorithms for Drawing Planar Graphs},
author={Baur, Melanie},
address={Konstanz},
school={Universität Konstanz}
}RDF
<rdf:RDF
xmlns:dcterms="http://purl.org/dc/terms/"
xmlns:dc="http://purl.org/dc/elements/1.1/"
xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
xmlns:bibo="http://purl.org/ontology/bibo/"
xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
xmlns:foaf="http://xmlns.com/foaf/0.1/"
xmlns:void="http://rdfs.org/ns/void#"
xmlns:xsd="http://www.w3.org/2001/XMLSchema#" >
<rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/20228">
<dc:creator>Baur, Melanie</dc:creator>
<dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/20228/2/Diss_Baur.pdf"/>
<dc:contributor>Baur, Melanie</dc:contributor>
<dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dc:language>eng</dc:language>
<dcterms:abstract xml:lang="eng">In this thesis, we consider properties of triconnected, planar graphs and devote ourselves to the concepts canonical ordering and Schnyder woods. Whereas these concepts mostly have been investigated separately so far, we focus this thesis on their similarities and connection points, and present them consistently for the first time.<br /><br /><br /><br />The title "Combinatorial Concepts and Algorithms for Drawing Planar Graphs" already reflects the twofold structure of this thesis.<br /><br />In Part I "Concepts" we introduce, after giving a summary of fundamental properties of planar graphs, the combinatorial concepts of canonical ordering and Schnyder woods. Furthermore, we reveal their connection to triangle contact representations.<br /><br />Canonical ordering and Schnyder woods have manifold applications in graph encoding, in dimension theory, in the area of counting various kinds of planar maps, and more.<br /><br />We concentrate on graph drawing, in particular on triangle contact representations, and present in Part II "Algorithms" appropriate detailed and consistent algorithms with focus on the implementation of the leftist canonical ordering.<br /><br /><br /><br />Main contributions of this thesis are the introduction of the concept of leftist canonical ordering, the establishing of a connection via ordered path partitions to minimal Schnyder woods, and the provision of efficient algorithms with detailed pseudocodes that ease coding.<br /><br />Based on these, we show how and on which graph classes these methods can be used to determine homothetic triangle contact representations. Furthermore, we give an extensive overview of related concepts in a consistent manner and provide various new, simpler or more consistent proofs and algorithms.</dcterms:abstract>
<dcterms:alternative>Kombinatorische Konzepte und Algorithmen zum Zeichnen planarer Graphen</dcterms:alternative>
<void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
<dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
<dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dcterms:title>Combinatorial Concepts and Algorithms for Drawing Planar Graphs</dcterms:title>
<dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2012-08-27T06:48:26Z</dc:date>
<dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/20228/2/Diss_Baur.pdf"/>
<dcterms:issued>2012</dcterms:issued>
<bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/20228"/>
<foaf:homepage rdf:resource="http://localhost:8080/"/>
<dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2012-08-27T06:48:26Z</dcterms:available>
<dc:rights>terms-of-use</dc:rights>
</rdf:Description>
</rdf:RDF>
