Level Planarity

Definition

A graph is level planar if it can be embedded in the plane such that no two edges cross and the vertices lie on some prescribed horizontal lines.

Formally, in Level Planarity, the directed graph \(G=(V,E)\) is equipped with a function \(\gamma : V \mapsto \{1,2,\ldots,k\}\) with \(k\in\mathbb{N}\) such that for every edge \((u,v)\in E\) it is \(\gamma(u)<\gamma(v)\). The level graph is called proper if it is \(\gamma(u)+1=\gamma(v)\) for every edge. With \(V_i=\gamma^{-1}(i)\) we denote all vertices on level \(i\). A level planar drawing maps all vertices \(v\in V_I\) of a level \(i\) to a point on the line \(y=i\) such that every edge is y-monotone and no two edges cross. A level graph is level planar if it admits a level planar drawing.

Complexity

Jünger, Leipert, and Mutzel (1998) give a linear-time algorithm for testing level planarity. While the dissertation by Leipert (1998) describes a prototypical implementation, no implementations exist of this algorithm. Brückner (2021) gives an alternative linear-time algorithms and points out some issues with the algorithm by Jünger, Leipert, and Mutzel (1998). Simpler algorithms with a super-linear runtime have been proposed (Harrigan and Healy 2007; Randerath et al. 2001; Brückner, Rutter, and Stumpf 2022; Fulek et al. 2012). For these, we could only find an implementation by Estrella-Balderrama, Fowler, and Kobourov (2010) for the quadratic algorithm by Harrigan and Healy (2007).

Related Problems

Trivially reduces to Proper Clustered Level Planarity by making the instances proper (i.e., inserting subdivision vertices on edges spanning multiple levels) and adding all vertices to the same (root-)cluster (Da Lozzo 2015, Theorem 7.4).

Reduces to Strip Planarity by converting each level to three strips and subdividing the edges appropriately (Da Lozzo 2015, Theorem 9.3).

Reduces to Radial Level Planarity by adding a single edge that spans from the lowest to the highest level, at which the radial drawing can be cut to a planar one (Schaefer 2013, Lemma 6.12).

See Also

• Planarity Variants for Directed Graphs Brückner (2021)

References

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.

Da Lozzo, Giordano. 2015. “Planar Graphs with Vertices in Prescribed Regions:models, Algorithms, and Complexity.” PhD thesis, Roma Tre University. http://www.dia.uniroma3.it/~dalozzo/files/phd-thesis-giordano-dalozzo.pdf.

Estrella-Balderrama, Alejandro, J. Joseph Fowler, and Stephen G. Kobourov. 2010. “GraphSET, a Tool for Simultaneous Graph Drawing.” Software: Practice and Experience 40 (10): 849–63. https://doi.org/10.1002/spe.958.

Fulek, Radoslav, Michael J. Pelsmajer, Marcus Schaefer, and Daniel Štefankovič. 2012. “Hananitutte, Monotone Drawings, and Level-Planarity.” In Thirty Essays on Geometric Graph Theory, 263–87. Springer New York. https://doi.org/10.1007/978-1-4614-0110-0_14.

Harrigan, Martin, and Patrick Healy. 2007. “Practical Level Planarity Testing and Layout with Embedding Constraints.” In Graph Drawing, 15^th International Symposium, GD 2007, Sydney, Australia, September 24-26, 2007. Revised Papers, edited by Seok-Hee Hong, Takao Nishizeki, and Wu Quan, 4875:62–68. Lecture Notes in Computer Science. Springer. https://doi.org/10.1007/978-3-540-77537-9\_9.

Jünger, Michael, Sebastian Leipert, and Petra Mutzel. 1998. “Level Planarity Testing in Linear Time.” In Graph Drawing, 6^th International Symposium, GD’98, Montréal, Canada, August 1998, Proceedings, edited by Sue Whitesides, 1547:224–37. Lecture Notes in Computer Science. Springer. https://doi.org/10.1007/3-540-37623-2_17.

Leipert, Sebastian. 1998. “Level Planarity Testing and Embedding in Linear Time.” PhD thesis, Universität zu Köln.

Randerath, Bert, Ewald Speckenmeyer, Endre Boros, Peter L. Hammer, Alexander Kogan, Kazuhisa Makino, Bruno Simeone, and Ondrej Cepek. 2001. “A Satisfiability Formulation of Problems on Level Graphs.” Electron. Notes Discret. Math. 9: 269–77. https://doi.org/10.1016/S1571-0653(04)00327-0.

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.