%0 Journal Article %1 krw-dgfcf-JGAA19 %A Kryven, Myroslav %A Ravsky, Alexander %A Wolff, Alexander %D 2019 %J Journal of Graph Algorithms & Applications %K %N 2 %P 371--391 %R 10.7155/jgaa.00495 %T Drawing Graphs on Few Circles and Few Spheres %V 23 %X 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.

@article{krw-dgfcf-JGAA19, abstract = {Given a drawing of a graph, its \emph{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 \emph{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 \emph{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.}, added-at = {2023-12-12T18:32:03.000+0100}, arxiv = {https://arxiv.org/abs/1709.06965}, author = {Kryven, Myroslav and Ravsky, Alexander and Wolff, Alexander}, biburl = {https://www.bibsonomy.org/bibtex/21da5866c5f6df80e25ffd16af18365b5/admin}, doi = {10.7155/jgaa.00495}, interhash = {13ab6722d6154193512f1c2b7c5d687b}, intrahash = {1da5866c5f6df80e25ffd16af18365b5}, journal = {Journal of Graph Algorithms \& Applications}, keywords = {}, number = 2, pages = {371--391}, slides = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/slides/krw-dgfcf-CALDAM18-slides.pdf}, timestamp = {2023-12-12T18:32:03.000+0100}, title = {Drawing Graphs on Few Circles and Few Spheres}, volume = 23, year = 2019 }