### 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 |

### Fingerprint

### ASJC Scopus subject areas

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

### Cite this

*Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms*(pp. 195-204). SIAM.

}

*Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms.*SIAM, pp. 195-204, Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, USA, 1/17/99.

**Nonplanar topological inference and political-map graphs.** / Chen, Zhi Zhong; He, Xin; Kao, Ming Yang.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Nonplanar topological inference and political-map graphs

AU - Chen, Zhi Zhong

AU - He, Xin

AU - Kao, Ming Yang

PY - 1999/1/1

Y1 - 1999/1/1

N2 - 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 V1, V2, ..., Vq of V, decide whether G has a planar embedding ε such that for every Vi, there is a face Vi in ε whose boundary intersects every connected component of the subgraph induced by Vi. This result also has an application in printed circuit board design.

AB - 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 V1, V2, ..., Vq of V, decide whether G has a planar embedding ε such that for every Vi, there is a face Vi in ε whose boundary intersects every connected component of the subgraph induced by Vi. This result also has an application in printed circuit board design.

UR - http://www.scopus.com/inward/record.url?scp=0032761489&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032761489&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0032761489

SP - 195

EP - 204

BT - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Anon, null

PB - SIAM

ER -