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 Citations (Scopus)

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

Printed circuit boards
Polynomials
Graph in graph theory
Mixed Graphs
Inclusion Relations
Printed Circuit Board
Induced Subgraph
Intersect
Connected Components
Planar graph
Polynomial time
Sharing
Arc of a curve
Partition
Face
Design

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.
Chen, Zhi Zhong ; He, Xin ; Kao, Ming Yang. / Nonplanar topological inference and political-map graphs. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. editor / Anon. SIAM, 1999. pp. 195-204
@inproceedings{b0511af65130438fac3189a264b920a5,
title = "Nonplanar topological inference and political-map graphs",
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.",
author = "Chen, {Zhi Zhong} and Xin He and Kao, {Ming Yang}",
year = "1999",
month = "1",
day = "1",
language = "English (US)",
pages = "195--204",
editor = "Anon",
booktitle = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "SIAM",

}

Chen, ZZ, He, X & Kao, MY 1999, Nonplanar topological inference and political-map graphs. in Anon (ed.), 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.

Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. ed. / Anon. SIAM, 1999. p. 195-204.

Research output: Chapter in Book/Report/Conference proceedingConference 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 -

Chen ZZ, He X, Kao MY. Nonplanar topological inference and political-map graphs. In Anon, editor, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM. 1999. p. 195-204