Drawing Graphs on Few Circles and Few Spheres
Drawing Graphs on Few Circles and Few Spheres
复制标题
在几个圆和几个球体上绘制图形
DOI：
10.1007/978-3-319-74180-2_14
复制
发表时间：
2017
影响因子：
2.5
通讯作者：
A. Wolff
中科院分区：
文献类型：
--
作者：
Myroslav Kryven;A. Ravsky;A. Wolff
给定一个图形的绘图，其视觉复杂度定义为绘图中几何实体的数量，例如，直线绘图中的线段数量或圆弧绘图中的圆弧数量（在2D中）。最近，Chaplick等人。[GD 2016]引入了一种不同的视觉复杂度度量，\n {仿射覆盖数}，这是在2D（3D）中覆盖图$G$的无交叉直线图的最小直线（或平面）数量。在本文中，我们引入\n {球面覆盖数}，这是在2D（或3D）中共同覆盖一个无交叉圆弧图的最小圆（或球）数。事实证明，球面覆盖有时比仿射覆盖小得多。此外，还有一些高度对称的图，它们具有对称的最佳球面覆盖，但显然没有对称的最佳仿射覆盖。对于完全，完全二部，柏拉图图，我们分析了他们的球形覆盖数，并比较它们的仿射覆盖数，以及他们的段和弧数。我们还链接到其他图形参数，如色数，树宽，和线性荫度的球形覆盖数。
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. Moreover, there are highly symmetric graphs that have symmetric optimum spherical covers but apparently no symmetric optimum affine cover. 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 chromatic number, treewidth, and linear arboricity.