Geodesic
Drawing outer-1-planar graphs revisited
Journal of Graph Algorithms and Applications, Tome 26 (2022) no. 1, pp. 59-73.

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

In a recent article (Auer et al., Algorithmica 2016) it was claimed that every outer-1-planar graph has a planar visibility representation of area $O(n\log n)$. In this paper, we show that this is wrong: There are outer-1-planar graphs that require $\Omega(n^2)$ area in any planar drawing. Then we give a construction (using crossings, but preserving a given outer-1-planar embedding) that results in an orthogonal box-drawing with $O(n\log n)$ area and at most two bends per edge.
DOI : 10.7155/jgaa.00581
Keywords: outer-1-planar graph, poly-line drawing, embedding-preserving, lower bound 
@article{JGAA_2022_26_1_a3,
     author = {Therese Biedl},
     title = {Drawing outer-1-planar graphs revisited},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {59--73},
     publisher = {mathdoc},
     volume = {26},
     number = {1},
     year = {2022},
     doi = {10.7155/jgaa.00581},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00581/}
}
TY  - JOUR
AU  - Therese Biedl
TI  - Drawing outer-1-planar graphs revisited
JO  - Journal of Graph Algorithms and Applications
PY  - 2022
SP  - 59
EP  - 73
VL  - 26
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00581/
DO  - 10.7155/jgaa.00581
LA  - en
ID  - JGAA_2022_26_1_a3
ER  - 
%0 Journal Article
%A Therese Biedl
%T Drawing outer-1-planar graphs revisited
%J Journal of Graph Algorithms and Applications
%D 2022
%P 59-73
%V 26
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00581/
%R 10.7155/jgaa.00581
%G en
%F JGAA_2022_26_1_a3
Therese Biedl. Drawing outer-1-planar graphs revisited. Journal of Graph Algorithms and Applications, Tome 26 (2022) no. 1, pp. 59-73. doi : 10.7155/jgaa.00581. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00581/

Cité par Sources :