## Abstract

Given a political map M, we define a mixed graph G where the vertices correspond to the districts on M, the arcs encode the inclusion relation between the districts, and the edges indicate the sharing of boundary points of the districts. We prove that such graphs can be recognized in nondeterministic polynomial time. We then prove that a natural subclass of such graphs can be recognized in O(nα(n) log n) time, where n is the number of vertices in the input graph and α(n) is an inverse of Ackermann's function. The main result is an O(nα(n)log n)-time algorithm for the following problem II: Given a planar graph G = (V, E) and a partition V_{1}, V_{2}, ..., V_{q} of V, decide whether G has a planar embedding ε such that for every V_{i}, there is a face V_{i} in ε whose boundary intersects every connected component of the subgraph induced by V_{i}. This result also has an application in printed circuit board design.

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

Title of host publication | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |

Editors | Anon |

Publisher | SIAM |

Pages | 195-204 |

Number of pages | 10 |

State | Published - Jan 1 1999 |

Event | Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA Duration: Jan 17 1999 → Jan 19 1999 |

### Other

Other | Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

City | Baltimore, MD, USA |

Period | 1/17/99 → 1/19/99 |

## ASJC Scopus subject areas

- Chemical Health and Safety
- Software
- Safety, Risk, Reliability and Quality
- Discrete Mathematics and Combinatorics