On the Complexity of Covering Vertices by Faces in a Planar Graph
Daniel A. Bienstock, Clyde L. Monma · SIAM Journal on Computing · 1988
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-time recognition algorithm for special cases of Steiner tree problems in graphs which are solvable in polynomial time.