KIT | KIT-Bibliothek | Impressum | Datenschutz

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.

Open Access Logo


Verlagsausgabe §
DOI: 10.5445/IR/1000130164
Veröffentlicht am 01.03.2021
Cover der Publikation
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 Scopus
Dimensions
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page