Geodesic
Drawing Planar Cubic 3-Connected Graphs with Few Segments: Algorithms Experiments
Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 4, pp. 561-588.

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

A drawing of a graph can be understood as an arrangement of geometric objects. In the most natural setting the arrangement is formed by straight-line segments. Every cubic planar 3-connected graph with $n$ vertices has such a drawing with only $n/2 + 3$ segments, matching the lower bound. This result is due to Mondal et al. [J. of Comb. Opt., 25], who gave an algorithm for constructing such drawings. We introduce two new algorithms that also produce drawings with $n/2 + 3$ segments. One algorithm is based on a sequence of dual edge contractions, the other is based on a recursion of nested cycles. We also show a flaw in the algorithm of Mondal et al. and present a fix for it. We then compare the performance of these three algorithms by measuring angular resolution, edge length and face aspect ratio of the constructed drawings. We observe that the corrected algorithm of Mondal et al. mostly outperforms the other algorithms, especially in terms of angular resolution. However, the new algorithms perform better in terms of edge length and minimal face aspect ratio. 
@article{JGAA_2017_21_4_a8,
     author = {Alexander Igamberdiev and Wouter Meulemans and Andr\'e Schulz},
     title = {Drawing {Planar} {Cubic} {3-Connected} {Graphs} with {Few} {Segments:} {Algorithms} & {Experiments}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {561--588},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2017},
     doi = {10.7155/jgaa.00430},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00430/}
}
TY  - JOUR
AU  - Alexander Igamberdiev
AU  - Wouter Meulemans
AU  - André Schulz
TI  - Drawing Planar Cubic 3-Connected Graphs with Few Segments: Algorithms & Experiments
JO  - Journal of Graph Algorithms and Applications
PY  - 2017
SP  - 561
EP  - 588
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00430/
DO  - 10.7155/jgaa.00430
LA  - en
ID  - JGAA_2017_21_4_a8
ER  - 
%0 Journal Article
%A Alexander Igamberdiev
%A Wouter Meulemans
%A André Schulz
%T Drawing Planar Cubic 3-Connected Graphs with Few Segments: Algorithms & Experiments
%J Journal of Graph Algorithms and Applications
%D 2017
%P 561-588
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00430/
%R 10.7155/jgaa.00430
%G en
%F JGAA_2017_21_4_a8
Alexander Igamberdiev; Wouter Meulemans; André Schulz. Drawing Planar Cubic 3-Connected Graphs with Few Segments: Algorithms & Experiments. Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 4, pp. 561-588. doi : 10.7155/jgaa.00430. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00430/

Cité par Sources :