# Multilevel Planarity

Barth, Lukas; Brückner, Guido; Jungeblut, Paul; Radermacher, Marcel

##### 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)$, nd 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.

 Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI) Publikationstyp Zeitschriftenaufsatz Publikationsmonat/-jahr 01.2021 Sprache Englisch Identifikator ISSN: 1526-1719 KITopen-ID: 1000130164 Erschienen in Journal of graph algorithms and applications Verlag Journal of Graph Algorithms and Applications (JGAA) Band 25 Heft 1 Seiten 151–170 Nachgewiesen in ScopusDimensions
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page