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.
展开▼
机译:给定一个图形,其视觉复杂度定义为图形中的几何实体数,例如,直线图形中的线段数或圆弧图形中的圆弧数(2D) 。最近,Chaplick等。 [GD 2016]引入了一种针对视觉复杂度的不同度量,仿射覆盖数,这是同时覆盖2D图$ G $的无交叉直线图形的最小线(或平面)数(3D )。在本文中,我们介绍了球面覆盖数,它是一起覆盖2D(或3D)无交叉圆弧图形的最小圆(或球)数。事实证明,球形盖有时比仿射盖小得多。对于完整,完整的二分图和柏拉图图,我们分析了它们的球面覆盖数并将它们与仿射覆盖数以及其段和弧数进行比较。我们还将球面覆盖数链接到其他图形参数,例如树宽和线性树状度。
展开▼