Geodesic
Multilevel Planarity
Journal of Graph Algorithms and Applications, Tome 25 (2021) no. 1, pp. 151-170.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00554
Keywords: graph drawing, planar graphs, level planarity, upward planarity 
@article{JGAA_2021_25_1_a7,
     author = {Lukas Barth and Guido Br\"uckner and Paul Jungeblut and Marcel Radermacher},
     title = {Multilevel {Planarity}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {151--170},
     publisher = {mathdoc},
     volume = {25},
     number = {1},
     year = {2021},
     doi = {10.7155/jgaa.00554},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00554/}
}
TY  - JOUR
AU  - Lukas Barth
AU  - Guido Brückner
AU  - Paul Jungeblut
AU  - Marcel Radermacher
TI  - Multilevel Planarity
JO  - Journal of Graph Algorithms and Applications
PY  - 2021
SP  - 151
EP  - 170
VL  - 25
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00554/
DO  - 10.7155/jgaa.00554
LA  - en
ID  - JGAA_2021_25_1_a7
ER  - 
%0 Journal Article
%A Lukas Barth
%A Guido Brückner
%A Paul Jungeblut
%A Marcel Radermacher
%T Multilevel Planarity
%J Journal of Graph Algorithms and Applications
%D 2021
%P 151-170
%V 25
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00554/
%R 10.7155/jgaa.00554
%G en
%F JGAA_2021_25_1_a7
Lukas Barth; Guido Brückner; Paul Jungeblut; Marcel Radermacher. Multilevel Planarity. Journal of Graph Algorithms and Applications, Tome 25 (2021) no. 1, pp. 151-170. doi : 10.7155/jgaa.00554. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00554/

Cité par Sources :