Nonplanar topological inference and political-map graphs

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₁, V₂, ..., 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.