Information Technology Reference
In-Depth Information
G
[
A
]
−
v
, which is also a connected component of
G
−
v
.Thus, we shrink the drawing
of
G
[
V
(
K
)
v
] is drawn very close to
v
and none of its edges
crosses an edge in the rest of the graph. In particular, by shrinking
G
[
V
(
K
)
∪
v
] so that
G
[
V
(
K
)
∪
v
] we do
not introduce a pair of edges crossing an odd number of times. We label all the cycles
in
G
[
V
(
K
)
∪
∪
v
] as processed. By repeating this for all the troublesome cut-vertices of
D
so that none of the edges incident to
v
C
crosses another edge an odd
number of times. Finally, we label
C
as processed.
b)
C
Shares a Vertex with an Already Processed Cycle.
Let
v
be a vertex on
C
belonging to an already processed cycle
C
p
. Since processed cycles are vertex disjoint,
the cycle
C
p
is unique. Since the edges of
C
p
areeven,theedges
v
1
v
and
v
2
v
of
C
p
adjacent to
v
are attached to
v
both from the “inside” or both from the “outside” of
C
.
Suppose the latter. (The other case is analogous.) We split the vertex
v
by replacing it
with two new vertices
v
and
v
connected by an edge. Every edge
uv
attaching to
v
from the “outside” of
C
is replaced by an edge
uv
(including the edges
v
1
v
and
v
2
v
).
All other edges
uv
are replaced by an edge
uv
. The cycle that is obtained from
C
p
by replacing
v
with
v
is then labeled as processed. Note that we can do such vertex-
splitting in
C
we modify
D
withoutintroducing any pair of edges crossing an odd number of times
by drawing
v
and
v
very close to
v
. After performing all necessary vertex splits for
vertices of
C
, we may apply the procedure in case a) to the modified cycle
C
.
It is easy to see that the algorithm terminates after a finite number of steps a) or b)
with all cycles processed. Let
G
denote the graph we obtain from
G
after processing
all the cycles of
G
[
A
] and
G
[
B
]. By applying the strong Hanani-Tutte theorem on
G
we obtain an embedding which can be easily modified so that the only vertices of
G
not incident to the outer face of
G
[
A
] or
G
[
B
] are the vertices
v
C
that form the
centers of the wheels. In particular,
G
[
A
] isdrawnintheouter face of
G
[
B
] and vice-
versa. In the resulting embedding we delete all the vertices
v
C
and contract the edges
between the pairs of vertices
v
,v
that were obtained by vertex-splits.
Thus, we obtain an embedding of
G
in which for every component
X
of
G
[
A
]
∪
G
[
B
], all vertices of
G
−X
are drawn in the outer face of
X
. By inserting the removed
parts of
G
back to
G
we obtain an embedding of
G
in which for every component
X
of
G
[
A
]
X
are drawn in the outer face of
X
. The theorem follows
by contracting each component of
G
[
A
]
∪
G
[
B
], all vertices of
G
−
∪
G
[
B
] to a point and applying Lemma 2.
4
Proof of Theorem 2
In this section we construct a family of even clustered drawings of flat clustered cycles
on more than two clusters that are not clustered planar. Thus, the straightforward gen-
eralization of the Hanani-Tutte theorem for graphs with three or more clusters is not
possible. For any
r
3,ourcounterexample is a clustered cycle
with
kr
vertices and
r
clusters. In ourclustered drawing the clusters are drawn as re-
gions bounded by a pair of rays emanating from the same vertex
p
. We call
p
the
center
of ourdrawing.
Topologically our construction is equivalent to a cylindrical drawing,where
c
clus-
ters are separated by vertical lines. For every odd integer
k>
0, we can describe the
≥
3 and any odd
k
≥
curve representing the cycle analytically as a height function
f
(
ʱ
)=sin
rk
+1
k
ʱ
on
