Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00100 Radial Level Planarity Testing and Embedding in Linear Time Christian Bachmaier , Franz J. Brandenburg , and Michael Forster Vol. 9, no. 1, pp. 53-97, 2005. Regular paper Abstract A graph with an ordered k-partition of the vertices is radial level planar if there is a strictly outward drawing on k concentric levels without crossings. Radial level planarity extends level planarity, where the vertices are placed on k horizontal lines and the edges are routed strictly downwards without crossings. The extension is characterised by rings, which are certain level non-planar biconnected components. Our main results are linear time algorithms for radial level planarity testing and for computing a radial level planar embedding. We introduce PQR-trees as a new data structure where R-nodes and associated templates for their manipulation are introduced to deal with rings. Our algorithms extend level planarity testing and embedding algorithms, which use PQ-trees.
|
Revised: June 2005. Submitted: February 2004. Communicated by Giuseppe Liotta |
Journal of Graph Algorithms and Applications |