![]() |
Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Eleventh International Symposium on Graph Drawing, GD 2003
DOI: 10.7155/jgaa.00100
Radial Level Planarity Testing and Embedding in Linear Time
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.
|
Journal Supporters
|