## Abstract

Given a planar graph G and a sequence C_{1},⋯, 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_{1},⋯C_{q} incurs only a logarithmic factor of overhead.

Original language | English (US) |
---|---|

Pages (from-to) | 408-434 |

Number of pages | 27 |

Journal | SIAM Journal on Computing |

Volume | 32 |

Issue number | 2 |

DOIs | |

State | Published - Feb 2003 |

## Keywords

- Planar embedding
- Planar graph
- Topological inference

## ASJC Scopus subject areas

- Computer Science(all)
- Mathematics(all)