On the Complexity of Covering Vertices by Faces in a Planar Graph

The pair (G, D) consisting of a planar graph G V, E) with n vertices together with a subset of d special vertices D 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(ckn) 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 0(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.