Geodesic
Drawing Graphs on Few Circles and Few Spheres
Journal of Graph Algorithms and Applications, Tome 23 (2019) no. 2, pp. 371-391.

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

Given a drawing of a graph, its visual complexity is defined as the number of geometrical entities in the drawing, for example, the number of segments in a straight-line drawing or the number of arcs in a circular-arc drawing (in 2D). Recently, Chaplick et al. [GD 2016] introduced a different measure for the visual complexity, the affine cover number, which is the minimum number of lines (or planes) that together cover a crossing-free straight-line drawing of a graph $G$ in 2D (3D). In this paper, we introduce the spherical cover number, which is the minimum number of circles (or spheres) that together cover a crossing-free circular-arc drawing in 2D (or 3D). It turns out that spherical covers are sometimes significantly smaller than affine covers. For complete, complete bipartite, and platonic graphs, we analyze their spherical cover numbers and compare them to their affine cover numbers as well as their segment and arc numbers. We also link the spherical cover number to other graph parameters such as treewidth and linear arboricity.
DOI : 10.7155/jgaa.00495
Keywords: visual complexity, affine cover, spherical cover, segment number, arc number 
@article{JGAA_2019_23_2_a9,
     author = {Myroslav Kryven and Alexander Ravsky and Alexander Wolff},
     title = {Drawing {Graphs} on {Few} {Circles} and {Few} {Spheres}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {371--391},
     publisher = {mathdoc},
     volume = {23},
     number = {2},
     year = {2019},
     doi = {10.7155/jgaa.00495},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00495/}
}
TY  - JOUR
AU  - Myroslav Kryven
AU  - Alexander Ravsky
AU  - Alexander Wolff
TI  - Drawing Graphs on Few Circles and Few Spheres
JO  - Journal of Graph Algorithms and Applications
PY  - 2019
SP  - 371
EP  - 391
VL  - 23
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00495/
DO  - 10.7155/jgaa.00495
LA  - en
ID  - JGAA_2019_23_2_a9
ER  - 
%0 Journal Article
%A Myroslav Kryven
%A Alexander Ravsky
%A Alexander Wolff
%T Drawing Graphs on Few Circles and Few Spheres
%J Journal of Graph Algorithms and Applications
%D 2019
%P 371-391
%V 23
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00495/
%R 10.7155/jgaa.00495
%G en
%F JGAA_2019_23_2_a9
Myroslav Kryven; Alexander Ravsky; Alexander Wolff. Drawing Graphs on Few Circles and Few Spheres. Journal of Graph Algorithms and Applications, Tome 23 (2019) no. 2, pp. 371-391. doi : 10.7155/jgaa.00495. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00495/

Cité par Sources :