Information Technology Reference
In-Depth Information
e
ʱ
e
ʱ
e
ʳ
e
ʲ
e
ʳ
e
ʲ
e
ʲ
C
ʱ
C
ʱ
e
ʱ
C
ʱ
v
ʱ
e
ʱ
e
ʳ
e
ʱ
e
ʳ
e
ʱ
e
ʳ
e
ʲ
e
ʲ
e
ʲ
u
ʱ
(a)
(b)
(c)
Fig. 3.
The setting for (a) Lemma 9, (b) Lemma 10, and (c) Lemma 11
e
ʱ
e
ʱ
P
ʲ
P
ʳ
C
ʱ
D
v
ʳ
v
ʲ
C
v
ʱ
u
ʱ
u
ʲ
u
ʳ
Fig. 4.
Illustration for the proof of Lemma 9
In the next three lemmata we deal with the following setting.Assume that there exist
con-edges
e
ʱ
,e
ʲ
,e
ʳ
∈
A
for distinct clusters
ʱ
,
ʲ
,and
ʳ
, respectively, such that
e
ʱ
↗
e
ʲ
and
e
ʱ
↗ e
ʳ
.SinceT
EST
2 fails on
A
,
e
ʲ
does not cross
e
ʳ
.Let
C
ʱ
be any of the two
facial cycles of
A
[
ʱ
] incident to
e
ʱ
, where a facial cycle of
A
[
ʱ
] is a simple cycle all of
whose edges appear on the boundary of a single face of
A
[
ʱ
].Assume w.l.o.g.that
e
ʱ
is crossed first by
e
ʲ
and then by
e
ʳ
when
C
ʱ
is traversed clockwise. See Fig. 3(a).
The next lemma presents a condition in which we can delete
e
ʱ
from
A
.
Lemma 9 (
S
IMPLIFICATION
4
).
Suppose thatthere exists nocon-edgeof
C
ʱ
different
from
e
ʱ
that has a conflict with bothacon-edgefor
ʲ
and a con-edgefor
ʳ
.Then,for
every planarset
S
of spanning trees for
A
, we have
e
ʱ
/
∈
S
.
Proof sketch.
See Fig.4.Let
u
ʱ
and
v
ʱ
(
u
ʲ
and
v
ʲ
,
u
ʳ
and
v
ʳ
) be the end-vertices
of
e
ʱ
(resp. of
e
ʲ
,of
e
ʳ
). By Property 1, a closed simple curve
can be drawn through
u
ʱ
,
u
ʲ
,
u
ʳ
,
v
ʱ
,
v
ʳ
,and
v
ʲ
, with
e
ʱ
,
e
ʲ
,and
e
ʳ
in its interior and every other con-edge
for
ʱ
,
ʲ
,and
ʳ
in its exterior. If
e
ʱ
∈
C
S
. Then, the path
P
ʲ
in
S
connecting
u
ʲ
and
v
ʲ
and the path
P
ʳ
in
S
connecting
u
ʳ
and
v
ʳ
cross
S
,then
e
ʲ
,e
ʳ
/
∈
C
ʱ
at different
edges
e
ʱ
and
e
ʱ
. Hence, the end-vertices of
e
ʱ
are on different sides of the cycle
D
composed of
P
ʲ
,of
P
ʳ
, and of the paths in
C
between
u
ʲ
and
u
ʳ
and between
v
ʲ
and
v
ʳ
. However, no con-edgefor
ʱ
in
S
crosses
D
, hence
S
does not connect
ʱ
.
The next two lemmata state conditions in which no planar set of spanning trees for
A
exists. Their statements are illustratedinFigs. 3(b) and 3(c), respectively; further, they
can be proved with arguments similar to the ones in the proof of Lemma 9.
Lemma 10 (
T
EST
3
).
Suppose thatthere exist con-edges
e
ʱ
,e
ʲ
,e
ʳ
∈
A
for clusters
ʱ
,
ʲ
, and
ʳ
, respectively,such that
e
ʱ
=
e
ʱ
,
e
ʱ
belongsto
C
ʱ
, and
e
ʱ
↗
e
ʲ
as well
