Common-face embeddings of planar graphs

Zhi Zhong Chen*, Xin He, Ming-Yang Kao

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


Given a planar graph G and a sequence C1,⋯, Cq, where each Ci 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 Fi in the embedding whose boundary contains at least one vertex from each set in Ci. 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 Ci, 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 Ci, each set in Ci 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 C1,⋯Cq incurs only a logarithmic factor of overhead.

Original languageEnglish (US)
Pages (from-to)408-434
Number of pages27
JournalSIAM Journal on Computing
Issue number2
StatePublished - Feb 2003


  • Planar embedding
  • Planar graph
  • Topological inference

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)


Dive into the research topics of 'Common-face embeddings of planar graphs'. Together they form a unique fingerprint.

Cite this