# zbMATH — the first resource for mathematics

Radial level planarity testing and embedding in linear time. (English) Zbl 1085.05025
Summary: 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.

##### MSC:
 05C10 Planar graphs; geometric and topological aspects of graph theory 05C85 Graph algorithms (graph-theoretic aspects) 68P05 Data structures 68R10 Graph theory (including graph drawing) in computer science
##### Keywords:
linear time algorithms
PORTA
Full Text: