Combinatorial Concepts and Algorithms for Drawing Planar Graphs

Cite This

Files in this item

Checksum: MD5:44c1b84b166b411645e68adb71f7c57f

BAUR, Melanie, 2012. Combinatorial Concepts and Algorithms for Drawing Planar Graphs [Dissertation]. Konstanz: University of Konstanz

@phdthesis{Baur2012Combi-20228, title={Combinatorial Concepts and Algorithms for Drawing Planar Graphs}, year={2012}, author={Baur, Melanie}, address={Konstanz}, school={Universität Konstanz} }

2012-08-27T06:48:26Z Baur, Melanie terms-of-use Kombinatorische Konzepte und Algorithmen zum Zeichnen planarer Graphen eng Baur, Melanie 2012 Combinatorial Concepts and Algorithms for Drawing Planar Graphs 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. 2012-08-27T06:48:26Z

Downloads since Oct 1, 2014 (Information about access statistics)

Diss_Baur.pdf 1032

This item appears in the following Collection(s)

Search KOPS


My Account