Algorithms for Incremental Planar Graph Drawing and Twopage Book Embeddings
Gronemann, Martin (2015) Algorithms for Incremental Planar Graph Drawing and Twopage Book Embeddings. PhD thesis.
Abstract
Subject of this work are two problems related to ordering the vertices of planar graphs. The first one is concerned with the properties of vertexorderings that serve as a basis for incremental drawing algorithms. Such a drawing algorithm usually extends a drawing by adding the vertices stepbystep as provided by the ordering. In the field of graph drawing several orderings are in use for this purpose. Some of them, however, lack certain properties that are desirable or required for classic incremental drawing methods. We narrow down these properties, and introduce the bitonic stordering, an ordering which combines the features only available when using canonical orderings with the flexibility of storderings. The additional property of being bitonic enables an stordering to be used in algorithms that usually require a canonical ordering. With this in mind, we describe a lineartime algorithm that computes such an ordering for every biconnected planar graph. Unlike canonical orderings, storderings extend to directed graphs, in particular planar stgraphs. Being able to compute bitonic storderings for planar stgraphs is of particular interest for upward planar drawing algorithms, since traditional incremental algorithms for undirected planar graphs might be adapted to directed graphs. Based on this observation, we give a full characterization of the class of planar stgraphs that admit such an ordering. This includes a lineartime algorithm for recognition and ordering. Furthermore, we show that by splitting specific edges of an instance that is not part of this class, one is able to transform it into one for which then such an ordering exists. To do so, we describe a lineartime algorithm for finding the smallest set of edges to split. We show that for a planar stgraph G=(V,E), V−3 edge splits are sufficient and every edge is split at most once. This immediately translates to the number of bends required for upward planar polyline drawings. More specifically, we show that every planar stgraph admits an upward planar polyline drawing in quadratic area with at most V−3 bends in total and at most one bend per edge. Moreover, the drawing can be obtained in linear time. The second part is concerned with embedding planar graphs with maximum degree three and four into books. Besides providing a simplified incremental lineartime algorithm for embedding triconnected 3planar graphs into a book of two pages, we describe a lineartime algorithm to compute a subhamiltonian cycle in a triconnected 4planar graph.
Download: 
PDF
Download (1MB) 

Editorial actions:  View Item (Login required) 
Item Type:  Thesis (PhD) 

Citations:  No citation data. 
Uncontrolled Keywords:  
Subjects: 

Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Juenger 
Related URLs: 
ZAIK Number:  UNSPECIFIED 

Depositing User:  Martin Gronemann 
Date Deposited:  12 Mar 2018 14:18 
Last Modified:  12 Mar 2018 15:06 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/922 