Circle Planarity of Level Graphs
Christian Bachmaier, Franz Josef Brandenburg · 2005
In this thesis we generalise the notion of level planar graphs in two directions: track planarity and radial planarity. Our main results are linear time algorithms both for the planarity test and for the computation of an embedding, and thus a drawing. Our algorithms use and generalise PQ-trees, which are a data structure for efficient planarity tests. A graph is a level graph, if it has a partition of the vertices in levels such that the vertices of each level can be placed on a horizontal line and the edges are strictly downwards. It is level planar if there are no edge crossings. Level planarity can be tested efficiently in linear time by sophisticated and complex algorithms. Level graphs exclude horizontal edges between vertices on the same level. Such edges are allowed by our track graphs. In radial level graphs the vertices of each level are placed on concentric circles and the edges are outwards. We characterise essential differences between level and radial level planar graphs, which are expressed by level non-planar biconnected components called rings. The presence of rings introduces the particular problem of the nesting of non-connected components. Further, we