Common-Face Embeddings of Planar Graphs
Zhi‐Zhong Chen, Xin He, Ming‐Yang Kao · SIAM Journal on Computing · 2003
Given a planar graph $\Ggg$ and a sequence ${\CC}_1,\ldots,{\CC}_q$, where each ${\CC}_i$ is a family of vertex subsets of $\Ggg$, we wish to find a plane embedding of $\Ggg$, if any exists, such that, for each $i\in\{1,\ldots,q\}$, there is a face F i in the embedding whose boundary contains at least one vertex from each set in CC i . This problem has applications in the recovery of topological information from geographical data and the design of constrained layouts in VLSI. Let $\inputsize$ be the input size,i.e., the total number of vertices and edges in $\Ggg$ and the families CC i , counting multiplicity. We show that this problem is NP-complete in general. We also show that it is solvable in $O(\inputsize\log \inputsize)$ time for the special case in which, for each input family CC i , each set in CC i induces a connected subgraph of the input graph $\Ggg$. 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 CC 1 , . . .,CC q incurs only a logarithmic factor of overhead.