Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00495
Drawing Graphs on Few Circles and Few Spheres
Vol. 23, no. 2, pp. 371-391, 2019. Regular paper.
Abstract 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.
|
Submitted: March 2018.
Reviewed: August 2018.
Revised: March 2019.
Accepted: April 2019.
Final: April 2019.
Published: June 2019.
Communicated by
Henk Meijer
|
Journal Supporters
|