Common-Face Embeddings of Planar Graphs

Original · EN

Given a planar graph G and a sequence C₁,...,Cq, where each Cᵢ 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 in 1,...,q, there is a face Fᵢ in the embedding whose boundary contains at least one vertex from each set in Cᵢ. This problem has applications to 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 and edges in G and the families Cᵢ, 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 where for each input family Cᵢ, each set in Cᵢ 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₁,...,Cq only incurs a logarithmic factor of overhead.