Radial Level Planarity

Definition

Radial Level Planarity is a generalization of Level Planarity where levels are not represented by axis-parallel lines, but by concentric rings. Equivalently, this can be seen as drawing the horizontal levels on a standing torus instead of in the plane.

Complexity

Testing level planarity can be reduced to the radial variant by introducing an edge from the lowest to the highest level, at which the cylinder can be cut to transform a radial solution back into the plane. Bachmaier et al. give a linear-time algorithm for testing radial level planarity Bachmaier, Brandenburg, and Forster (2005). While the dissertation by Bachmaier (2004) describes a prototypical implementation, no implementations exist of this algorithm. Brückner (2021) points out some issues with the algorithm by Bachmaier, Brandenburg, and Forster (2005). A simple polynomial-time algorithm is suggested by Brückner, Rutter, and Stumpf (2022).

See Also

References

Bachmaier, Christian. 2004. “Circle Planarity of Level Graphs.” PhD thesis, University of Passau, Germany. http://www.opus-bayern.de/uni-passau/volltexte/2004/38/index.html.
Bachmaier, Christian, Franz-Josef Brandenburg, and Michael Forster. 2005. “Radial Level Planarity Testing and Embedding in Linear Time.” Journal of Graph Algorithms and Applications 9 (1): 53–97. https://doi.org/10.7155/jgaa.00100.
Brückner, Guido. 2021. “Planarity Variants for Directed Graphs.” PhD thesis, Karlsruhe Institute of Technology, Germany. https://nbn-resolving.org/urn:nbn:de:101:1-2021080405022988868936.
Brückner, Guido, Ignaz Rutter, and Peter Stumpf. 2022. “Level-Planarity: Transitivity Vs. Even Crossings.” The Electronic Journal of Combinatorics 29 (4). https://doi.org/10.37236/10814.
Schaefer, Marcus. 2013. “Toward a Theory of Planarity: Hanani-Tutte and Planarity Variants.” Journal of Graph Algorithms and Applications 17 (4): 367–440. https://doi.org/10.7155/jgaa.00298.