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.
%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 gd-info1 myown
%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 = {2024-07-14T10:03:47.000+0200},
arxiv = {https://arxiv.org/abs/1709.06965},
author = {Kryven, Myroslav and Ravsky, Alexander and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/21da5866c5f6df80e25ffd16af18365b5/awolff},
doi = {10.7155/jgaa.00495},
interhash = {13ab6722d6154193512f1c2b7c5d687b},
intrahash = {1da5866c5f6df80e25ffd16af18365b5},
journal = {Journal of Graph Algorithms \& Applications},
keywords = {gd-info1 myown},
number = 2,
pages = {371--391},
slides = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/slides/krw-dgfcf-CALDAM18-slides.pdf},
timestamp = {2024-07-14T10:03:47.000+0200},
title = {Drawing Graphs on Few Circles and Few Spheres},
volume = 23,
year = 2019
}