Line and Plane Cover Numbers Revisited
Line and Plane Cover Numbers Revisited
复制标题
重新审视线和平面覆盖号码
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
A. Wolff
中科院分区：
文献类型：
--
作者：
T. Biedl;S. Felsner;H. Meijer;A. Wolff
无直线交叉图的视觉复杂度的一个度量是覆盖所有顶点所需的最小线数。对于一个给定的图$G$，这样的最小数（在{2，3}$中所有d维图上）称为n {$d$-维弱线覆盖数}，记为$pi^1_d（G）$。在3D中，覆盖~$G$的所有顶点所需的最小n {planes}数量表示为$pi^2_3（G）$。当边缘也需要被覆盖时，相应的数字$
ho^1_d（G）$和$
ho^2_3（G）$称为G的线覆盖数和平面覆盖数.
计算这些覆盖数中的任何一个--除了$pi^1_2（G）$ --都是NP难的。计算$pi^1_2（G）$的复杂性由Chaplick等人提出作为一个开放问题。[WADS 2017]。本文证明了对给定的平面图G$，判定$pi^1_2（G）=2$是NP-难的.本文进一步证明了深度为d的通用叠层三角剖分G_d有pi ^1_2（G_d）=d+1$。关于3D，我们证明了任意n$-顶点图G$，
ho^2_3（G）=2$最多有5 n-19$条边，这是紧的.
A measure for the visual complexity of a straight-line crossing-free drawing of a graph is the minimum number of lines needed to cover all vertices. For a given graph $G$, the minimum such number (over all drawings in dimension $d in {2,3}$) is called the emph{$d$-dimensional weak line cover number} and denoted by $pi^1_d(G)$. In 3D, the minimum number of emph{planes} needed to cover all vertices of~$G$ is denoted by $pi^2_3(G)$. When edges are also required to be covered, the corresponding numbers $
ho^1_d(G)$ and $
ho^2_3(G)$ are called the emph{(strong) line cover number} and the emph{(strong) plane cover number}.
Computing any of these cover numbers -- except $pi^1_2(G)$ -- is known to be NP-hard. The complexity of computing $pi^1_2(G)$ was posed as an open problem by Chaplick et al. [WADS 2017]. We show that it is NP-hard to decide, for a given planar graph~$G$, whether $pi^1_2(G)=2$. We further show that the universal stacked triangulation of depth~$d$, $G_d$, has $pi^1_2(G_d)=d+1$. Concerning~3D, we show that any $n$-vertex graph~$G$ with $
ho^2_3(G)=2$ has at most $5n-19$ edges, which is tight.
几条线上的 4 连通三角剖分
DOI：
10.1007/978-3-030-35802-0_30
发表时间：
2019
期刊：
影响因子：
--
作者：
S. Felsner
通讯作者：
S. Felsner