Combinatorial Concepts and Algorithms for Drawing Planar Graphs

Abstract

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.