Multilevel Planarity
Vol. 25, no. 1, pp. 151-170, 2021. Regular paper.
Abstract In this paper, we introduce and study multilevel planarity, a generalization of upward planarity and level planarity. Let $G = (V, E)$ be a directed graph and let $\ell: V \to \mathcal P(\mathbb Z)$ be a function that assigns a finite set of integers to each vertex. A multilevel-planar drawing of $G$ is a planar drawing of $G$ such that for each vertex $v\in V$ its $y$-coordinate $y(v)$ is in $\ell(v)$, and each edge is drawn as a strictly $y$-monotone curve. We present linear-time algorithms for testing multilevel planarity of embedded graphs with a single source and of oriented cycles. Complementing these algorithmic results, we show that multilevel-planarity testing is $\textsf{NP}$-complete even in very restricted cases.

 This work is licensed under the terms of the CC-BY license.
Submitted: January 2020.
Reviewed: December 2020.
Revised: January 2021.
Accepted: January 2021.
Final: January 2021.
Published: January 2021.
Communicated by Giuseppe Di Battista
article (PDF)