×

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
Software:
PORTA
PDF BibTeX XML Cite
Full Text: DOI EuDML EMIS