Common-face embeddings of planar graphs

Given a planar graph G and a sequence C₁,⋯, C_q, where each C_i is a family of vertex subsets of G, we wish to find a plane embedding of G, if any exists, such that, for each i ε {1,⋯,q}, there is a face F_i in the embedding whose boundary contains at least one vertex from each set in C_i. This problem has applications in the recovery of topological information from geographical data and the design of constrained layouts in VLSI. Let I be the input size, i.e., the total number of vertices the edges in G and the families C_i, counting multiplicity. We show that this problem is NP-complete in general. We also show that it is solvable in O(I log I) time for the special case in which, for each input family C_i, each set in C_i induces a connected subgraph of the input graph G. Note that the classical problem of simply finding a planar embedding is a further special case of this case with q = 0. Therefore, the processing of the additional constraints C₁,⋯C_q incurs only a logarithmic factor of overhead.