On the Complexity of Covering Vertices by Faces in a Planar Graph
On the Complexity of Covering Vertices by Faces in a Planar Graph
复制标题
关于平面图中面覆盖顶点的复杂性
DOI：
10.1137/0217004
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
C. Monma
中科院分区：
文献类型：
--
作者：
D. Bienstock;C. Monma
由n个顶点的平面图$G=(V，E)$和d个特殊顶点的子集$D\subseteq V$组成的对$(G，D)$称为k-平面，如果G在平面上有嵌入，使得至多需要G的k个面来覆盖D中的所有顶点。1-平面性检查可以在线性时间内完成，因为它归结为检查相关图的平面性的问题。我们给出了一个算法，给定一个图G和一个值k，它可以确定G不是k-平面的，或者在$O(c^k n)$时间内生成一个适当的嵌入和相关的最小覆盖，其中c是一个常数。因此，对于任何固定的k，该算法都是线性时间的。由于我们还证明了，对于任意k，相关的决策问题是强NP-完全的，即使当平面图本质上有唯一的平面嵌入$d=\theta(N)$，并且所有的面圈都有有界长度时，算法所需的时间在k中呈指数增长。这些结果提供了一个多项式-t。
The pair $(G,D)$ consisting of a planar graph $G = (V,E)$ with n vertices together with a subset of d special vertices $D \subseteq V$ is called k-planar if there is an embedding of G in the plane so that at most k faces of G are required to cover all of the vertices in D. Checking 1-planarity can be done in linear-time since it reduces to a problem of checking planarity of a related graph. We present an algorithm which given a graph G and a value k either determines that G is not k-planar or generates an appropriate embedding and associated minimum cover in $O(c^k n)$ time, where c is a constant. Hence, the algorithm runs in linear time for any fixed k. The fact that the time required by the algorithm grows exponentially in k is to be expected since we also show that for arbitrary k, the associated decision problem is strongly NP-complete, even when the planar graph has essentially a unique planar embedding, $d = \theta (n)$, and all facial cycles have bounded length. These results provide a polynomial-t...