Nonplanar topological inference and political-map graphs

Zhi Zhong Chen*, Xin He, Ming Yang Kao

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations

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

Original languageEnglish (US)
Title of host publicationProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Editors Anon
PublisherSIAM
Pages195-204
Number of pages10
StatePublished - Jan 1 1999
EventProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA
Duration: Jan 17 1999Jan 19 1999

Other

OtherProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms
CityBaltimore, MD, USA
Period1/17/991/19/99

    Fingerprint

ASJC Scopus subject areas

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

Cite this

Chen, Z. Z., He, X., & Kao, M. Y. (1999). Nonplanar topological inference and political-map graphs. In Anon (Ed.), Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 195-204). SIAM.