Clustered Planarity Testing Revisited - Graph Drawing - page 433

3.1 Proof of Theorem 1

The proof is inspired by the proof of the strong Hanani-Tutte theorem from [33] and
its outline is as follows. First we obtain a subgraph G of G containing the boundary of
each component of G [ A ] and G [ B ] and such that each of G [ A ] and G [ B ] is a cactus
forest ,thatis,agraph where every two cycles are edge disjoint. Equivalently, a cactus
forest is a graph with no subdivision of K 4 −

e . A connected component of a cactusfor-

est is called a cactus .
Then we apply the strong Hanani-Tutte theorem on a graph which is constructed
from G by turning all cycles in G [ A ] and G [ B ] into wheels, and by splitting certain
vertices of G into edges. The wheels in G guarantee that everything that has been
removed from G in order to obtain G can be inserted back.
Let X 1 ,...,X k denote the connected components of G [ A ] and G [ B ]. By Lemma 1
we find an exposed embedding

( X i ) of each X i .Let X i denote the subgraph of X i
obtained by deleting from X i all the vertices and edges not incident to the outer face of
D

D

( X i ). Observe that X i is a cactus.

Let G =( i =1 X i )+ E ( A, B ).Thatis, G is subgraph of G that consists of all
X i -s and all edges between the two clusters. Let D denote the drawing of G obtained

from the initial independently even drawing of G by deleting the edges and vertices of
G not belonging to G .Thus,

D is independently even.
In what follows we process the cycles of G [ A ] and G [ B ] one by one. We will be
modifying G and therefore also the drawing D . At each stageofthisprocesssome

cycles in G [ A ] and G [ B ] will be labeled as processed and the rest will be labeled as
unprocessed. We will maintain the property that all processed cycles are vertex disjoint
and that all their edges are even. We start with all the cycles in G [ A ] and G [ B ] being
labeled as unprocessed. Let C denote an unprocessed cycle in G [ A ]. For cycles in
G [ B ], the procedure is analogous. We consider two cases.
a) C Shares no Vertex with an Already Processed Cycle. We two-color the con-
nected regions in the complement of C so that two regions sharing a non-trivial part
of the boundary receive opposite colors. We say that a point not lying on C is “out-
side” of C if it is contained in the region with the same color as the unbounded region.
Otherwise, such a point is “inside” of C .
We locally modify the drawing

D at the vertices of C so that all the edges of C
cross every other edgeanevennumber of times [33]. Since D is a clustered drawing

of G , all vertices of B are “outside” of C . Therefore, every path joining C with a
vertex in B internally vertex disjoint from C is attached to its endpoint on C from the
“outside” of C .
Now we fill the cycle C with a wheel. More precisely, we add a vertex v C into A and
place it very close to an arbitrary vertex of C “inside” of C . We connect v C with all the
vertices of C by edges that closely follow the closed curve representing C either from
the left or from the right, and attach to their endpoints on C from “inside”. Portions
of these new edges may lie “outside” of C due to self-crossingsof C ,but not in the
neighborhood of vertices of C . Therefore, the new edges can introduce an odd crossing
pair only with an edge e attached to a vertex v of C from the “inside” of C .
Since G [ A ] is a cactus forest, it follows that such a vertex v is a cutvertexin G [ A ]
and that the endpoint of e different from v belongs to a connected component K of