Combinatorial Concepts and Algorithms for Drawing Planar Graphs

Lade...
Vorschaubild
Dateien
Diss_Baur.pdf
Diss_Baur.pdfGröße: 3.14 MBDownloads: 689
Datum
2012
Autor:innen
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
ArXiv-ID
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz
Gesperrt bis
Titel in einer weiteren Sprache
Kombinatorische Konzepte und Algorithmen zum Zeichnen planarer Graphen
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Dissertation
Publikationsstatus
Published
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)
004 Informatik
Schlagwörter
kanonische Ordnung, Schnyder-Wald, Kontaktrepräsentation, dreifacher Zusammenhang, canonical ordering, Schnyder wood, triangle contact representation, triconnectedness, algorithm, graph theory, planar graph drawing, combinatorics
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690BAUR, Melanie, 2012. Combinatorial Concepts and Algorithms for Drawing Planar Graphs [Dissertation]. Konstanz: University of Konstanz
BibTex
@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.&lt;br /&gt;&lt;br /&gt;&lt;br /&gt;&lt;br /&gt;The title "Combinatorial Concepts and Algorithms for Drawing Planar Graphs" already reflects the twofold structure of this thesis.&lt;br /&gt;&lt;br /&gt;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.&lt;br /&gt;&lt;br /&gt;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.&lt;br /&gt;&lt;br /&gt;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.&lt;br /&gt;&lt;br /&gt;&lt;br /&gt;&lt;br /&gt;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.&lt;br /&gt;&lt;br /&gt;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>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
URL der Originalveröffentl.
Prüfdatum der URL
Prüfungsdatum der Dissertation
July 10, 2012
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen