Information Technology Reference
In-Depth Information
proof uses topological arguments to establish that the only con-edgefor
μ
in
S
\
S
has
its end-vertices in different connected components of the graph obtained from
S
[
μ
] by
removing the only con-edgefor
μ
in
S
Next, we study non-isomorphic spokes. Let
e
i
ʱ
be a spoke of the
ʱ
-donutfor
e
ʱ
.
Assume that
L
1
(
e
i
ʱ
) contains a con-edge
e
i
ʲ
for a cluster
ʲ
,andthat
H
1
(
e
i
ʱ
) contains a
con-edge
e
ʳ
for a cluster
ʳ
,where
e
i
ʱ
↗
\
S
.
e
ʳ
.ByProperty 1, since
e
ʳ
and
e
i
ʱ
belong to the same connected component of
K
A
and do not cross (as otherwise T
EST
2would succeed), it follows that
e
ʳ
does not cross any con-edgefor
ʱ
, hence it lies in
one of the two faces
f
ʱ
and
f
i
+1
e
i
ʲ
and
e
i
ʲ
↗
of
A
[
ʱ
] that
e
i
ʱ
shares with spokes
e
i−
1
and
e
i
+1
ʱ
,
ʱ
ʱ
respectively. Assume w.l.o.g.that
e
ʳ
lies in
f
i
+1
. By Lemma 12,
L
1
(
e
i
+
ʱ
) contains a
ʱ
con-edge
e
i
+1
ʲ
e
i
+
ʲ
.
The next two lemmata discuss the case in which
M
(
e
i
+
ʱ
) contains a con-edgefor
ʳ
that has a conflict with
e
i
+1
ʲ
for
ʲ
,where
e
i
+1
ʱ
↗
and the case in which it does not. We start with the latter.
Lemma 15 (
S
IMPLIFICATION
6
).
Suppose that nocon-edge
e
i
+1
ʳ
for
ʳ
exists such that
e
i
+1
ʳ
e
i
+1
ʲ
, andthat a planarset
S
of spanning trees for
A
exists. Then,
e
i
ʱ
∈
↗
S
.
Proof sketch.
If a planar set
S
of spanning trees for
A
exists with
e
i
ʱ
/
∈
S
,thenby
Lemma 5 we have
e
i
ʲ
∈
S
. Then, the paths
P
ʱ
and
P
ʳ
connecting the
end-vertices of
e
i
ʱ
and
e
ʳ
,together with a closed simple curve
S
and
e
ʳ
/
∈
C
surrounding
e
i
ʱ
,
e
i
ʲ
,
and
e
ʳ
form a closed curve
D
that contains vertices in
ʲ
on both sides. However,
D
cannot be crossed by any con-edgefor
ʲ
in
S
,thus
S
does not connect
ʲ
.
Lemma 16 (
S
IMPLIFICATION
7).
Suppose that a con-edge
e
i
+1
ʳ
for
ʳ
exists with
e
i
+1
ʳ
↗
e
i
+1
ʲ
.Ifa planarset
S
of spanning trees for
A
exists, then either
e
i
ʱ
∈
S
or
e
i
+1
ʱ
∈
S
.
Proof sketch.
By Lemma 13, at most one outof
e
i
ʱ
and
e
i
+1
belongsto
S
. To prove
ʱ
that at least one outof
e
i
ʱ
and
e
i
+1
belongsto
S
, by Lemma 5 it suffices to prove that
ʱ
at most one outof
e
i
ʲ
and
e
i
+1
belongsto
S
. This is accomplished again by Lemma 13
ʲ
and by proving that
e
i
+1
ʲ
is a spoke of the
ʲ
-donutfor
e
i
ʲ
.
Observe that Simplification 7 can be applied in the case in which the
ʱ
-donutfor
e
ʱ
has at least three spokes. Namely, in that case, by Lemmata 13 and 16 all the spokes
different from
e
i
ʱ
and
e
i
+
ʱ
can be removed from
A
.
Next, assume that there exists an
ʱ
-donut with exactly two spokes
e
ʱ
and
e
ʱ
. Con-
sider the smallest
j
1 such that one of the following holds:
(1) there exist con-edges
e
μ
∈
≥
L
j
(
e
ʱ
) and
e
ʽ
∈
H
j−
1
(
e
ʱ
) for clusters
μ
and
ʽ
,resp.,
L
j
(
e
ʱ
) for
μ
such that
g
μ
↗
such that
e
μ
↗
e
ʽ
, and there exists no con-edge
g
μ
∈
g
ʽ
with
g
ʽ
con-edgefor
ʽ
in
H
j−
1
(
e
ʱ
),forsome
a, b
∈{
1
,
2
}
with
a
=
b
;or
H
j
(
e
ʱ
) and
e
ʽ
∈
L
j
(
e
ʱ
) for clusters
μ
and
ʽ
,resp.,such
(2) there exist con-edges
e
μ
∈
that
e
μ
↗
e
ʽ
, and there exists no con-edge
g
μ
∈
H
j
(
e
ʱ
) for
μ
such that
g
μ
↗
g
ʽ
with
g
ʽ
con-edgefor
ʽ
in
L
j
(
e
ʱ
),forsome
a, b
∈{
1
,
2
}
with
a
=
b
. We have the following.
Lemma 17 (
S
IMPLIFICATION
8).
Assumethat a planarset
S
of spanning trees for
A
exists. Then,
e
μ
∈
S
.
