Home | Issues | About JGAA | Instructions for Authors |
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
|
Journal Supporters
|