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 multilevelplanar 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 lineartime algorithms for testing multilevel planarity of embedded graphs with a single source and of oriented cycles.
Complementing these algorithmic results, we show that multilevelplanarity testing is $\textsf{NP}$complete even in very restricted cases.
This work is licensed under the terms of the CCBY license.

Submitted: January 2020.
Reviewed: December 2020.
Revised: January 2021.
Accepted: January 2021.
Final: January 2021.
Published: January 2021.
Communicated by
Giuseppe Di Battista
