Information Technology Reference
In-Depth Information
3
ʱ
C
2
ʱ
C
e
ʱ
e
ʲ
2
e
ʱ
e
ʱ
e
ʲ
m
e
ʲ
1
e
ʲ
3
1
ʱ
C
ʱ
C
e
ʱ
e
ʱ
ʱ
C
Fig. 5.
A partial representation of the
ʱ
-donutfor
e
ʱ
as
e
ʱ
↗
e
ʳ
.Assumethat
e
ʱ
is crossed first by
e
ʲ
andthen by
e
ʳ
when
C
ʱ
is traversed
clockwise. Then, noplanarsetofspanning trees for
A
exists.
Lemma 11 (
T
EST
4
).
Suppose thatcon-edges
e
ʱ
,e
ʱ
∈
A
for
ʱ
exist in
C
ʱ
, andsuch
that
e
ʱ
,
e
ʱ
, and
e
ʱ
occurin this order along
C
ʱ
, when clockwise traversing
C
ʱ
. Suppose
also thatthere exist con-edges
e
ʲ
,e
ʲ
∈
A
for
ʲ
and
e
ʳ
∈
A
for
ʳ
such that
e
ʱ
↗
e
ʲ
,
e
ʱ
↗
e
ʲ
.Then, noplanarsetofspanning trees for
A
exists.
If S
IMPLIFICATIONS
1-4 do not apply to
A
and T
ESTS
1-4 fail on
A
, then the con-
edges for a cluster
ʱ
that are crossed by con-edges for (at least) two other clusters have
anicestructure, that we call
ʱ
-donut
(see Fig. 5). Consider a con-edge
e
ʱ
∈
e
ʳ
, and
e
ʱ
↗
A
for
ʱ
crossing con-edges
e
ʲ
1
,...,e
ʲ
m
for clusters
ʲ
1
,...,ʲ
m
, with
m
≥
2.An
ʱ
-donut
for
e
ʱ
consists of a sequence
e
ʱ
,...,e
ʱ
,e
k
+1
of con-edges for
ʱ
with
k
≥
2, called
ʱ
ʱ
,...,
ʱ
,
k
+1
ʱ
ʱ
of facial cycles in
A
[
ʱ
],
spokes
of the
ʱ
-donut, of a sequence
C
C
C
=
C
and of sequences
e
ʲ
j
,...,e
ʲ
j
of con-edges for
ʲ
j
, for each 1
≤
j
≤
m
,such that the
k
:(a)
e
ʱ
=
e
ʱ
;(b)
e
i
ʱ
↗
e
i
ʲ
j
,forevery1
following hold for every 1
≤
i
≤
≤
j
≤
m
;(c)
i
ʱ
and
i
+1
ʱ
share edge
e
i
ʱ
;(d)edge
e
i
ʱ
is crossed by
e
i
ʲ
1
,...,e
i
ʲ
m
C
C
in this order when
C
i
ʱ
is traversed clockwise; (e) all the con-edges of
C
i
+1
ʱ
encountered when clockwise
C
i
+1
ʱ
from
e
i
ʱ
to
e
i
+1
do not cross any con-edgefor
ʲ
2
,...,ʲ
m
; and (f) all
traversing
ʱ
i
+1
ʱ
i
+1
ʱ
from
e
i
+1
ʱ
to
e
i
ʱ
do
the con-edges of
C
encountered when clockwise traversing
C
not cross any con-edgefor
ʲ
1
,...,ʲ
m−
1
. We have the following.
Lemma 12.
Fo r every con-edge
e
ʱ
∈
A
for
ʱ
,there exists an
ʱ
-donutfor
e
ʱ
.
Proof sketch.
Let
e
ʱ
=
e
ʱ
and let
C
ʱ
and
C
ʱ
be the facial cycles incident to
e
ʱ
.
Since S
IMPLIFICATION
1 does not apply to
A
,
ʱ
.Let
e
ʲ
1
,...,e
ʲ
m
be the con-
edges for
ʲ
1
,...,ʲ
m
, respectively, ordered as they cross
e
ʱ
when clockwise traversing
C
C
ʱ
=
C
ʱ
.SinceS
IMPLIFICATION
4 does not apply to
A
and T
ESTS
3-4 fail on
A
, a con-edge
e
ʱ
exists in
ʱ
that is crossed by con-edges
e
ʲ
1
,...,e
ʲ
m
C
for
ʲ
1
,...,ʲ
m
, respectively,
ʱ
;further, all the con-edges of
ʱ
encountered
in this order when clockwise traversing
C
C
ʱ
from
e
ʱ
to
e
ʱ
(from
e
ʱ
to
e
ʱ
) do not cross any con-edges
for
ʲ
2
,...,ʲ
m
(resp. for
ʲ
1
,...,ʲ
m−
1
). This argument is repeated for
i
=3
,...,k
to
determine a facial cycle
when clockwise traversing
C
i
ʱ
containing
e
i−
1
and to determine edges
e
i
ʱ
,e
i
ʲ
1
,...,e
i
ʲ
m
.
C
ʱ
