Multilevel Planarity

Abstract

In this paper, we introduce and study the multilevel-planarity testing problem, which is a generalization of upward planarity and level planarity. Let $G = (V, E)$ be a directed graph and let $\ell : V \rightarrow \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 the y-coordinate of each vertex $v \in V$ is $y(v) \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 NP-complete even in very restricted cases.

Publication
WALCOM: Algorithms and Computation. WALCOM 2019. Lecture Notes in Computer Science, vol 11355. Springer, Cham
Avatar
Lukas Barth
Algorithmics Researcher