Information Technology Reference
In-Depth Information
ʱ
of
A
[
ʱ
] is considered in which the two con-edges
that are crossed by con-edges for all of
ʲ
1
,...,ʲ
m
are
e
ʱ
and
e
ʱ
.
C
k
+1
ʱ
C
Eventually, facial cycle
=
The
ʱ
-donutfor
e
ʱ
can be computed efficiently. Further, we have the following
lemma, whose proof is similar to the one of Lemma 9.
Lemma 13.
Let
e
ʱ
,...,e
ʱ
be thespokes of the
ʱ
-donutfor
e
ʱ
.Then,ifa planarset
S
of spanning trees for
A
exists, it containsexactly oneof
e
ʱ
,...,e
ʱ
.
Consider a con-edge
e
for a cluster
ʱ
.The
conflicting structure
M
(
e
) of
e
is a se-
quence of sets
H
0
(
e
)
,L
1
(
e
)
,H
1
(
e
)
,L
2
(
e
)
,H
2
(
e
)
,...
of con-edges which correspond
to the layers of a BFS traversal starting at
e
of the connected component of
K
A
con-
taining
e
.Thatis:
H
0
(
e
)=
1,
L
i
(
e
) is the set of con-edges that cross
con-edges in
H
i−
1
(
e
) and that are not in
L
i−
1
(
e
),and
H
i
(
e
) is the set of con-edges
that cross con-edges in
L
i
(
e
) and that are not in
H
i−
1
(
e
).
We n ow s tudy the conflicting structures of the spokes
e
ʱ
,...,e
ʱ
of the
ʱ
-donutof
a con-edge
e
ʱ
for
ʱ
.Notwoedges in a set
H
i
(
e
ʱ
) or in a set
L
i
(
e
ʱ
) have a conflict,
as otherwise T
EST
2would succeed. Also, by Lemma 5, any planar set
S
of spanning
{
e
}
; then, for
i
≥
trees for
A
contains either all the edges in
i
H
i
(
e
ʱ
) or all the edges in
i
L
i
(
e
ʱ
).
Assume that
e
ʱ
has a conflict with at least two con-edges for other clusters. For
any 1
k
, we say that
e
i
ʱ
and
e
i
+
ʱ
have
isomorphic conflicting structures
if
they belong to isomorphic connected components of
K
A
and if the vertices of these
components that are in correspondence under the isomorphism represent con-edges for
the same cluster. Formally,
e
i
ʱ
and
e
i
+
ʱ
have isomorphic conflicting structures if there
exists a bijective mapping
ʴ
from the edges in
M
(
e
i
ʱ
) to the edges in
M
(
e
i
+
ʱ
) such
that: (1)
e
is a con-edgeforacluster
if and only if
ʴ
(
e
) is a con-edgefor
,forevery
e
≤
i
≤
∈
M
(
e
i
ʱ
);(2)
e
∈
H
j
(
e
i
ʱ
) if and only if
ʴ
(
e
)
∈
H
j
(
e
i
+
ʱ
),forevery
e
∈
M
(
e
i
ʱ
);
L
j
(
e
i
ʱ
) if and only if
ʴ
(
e
)
L
j
(
e
i
+
ʱ
),forevery
e
M
(
e
i
ʱ
);and(4)
e
(3)
e
f
if
and only if
ʴ
(
e
)
↗ ʴ
(
f
),forevery
e,f ∈ M
(
e
i
ʱ
). Observe that the isomorphism of two
conflicting structures can be tested efficiently.
We will prove in the following four lemmata that by examining the conflicting struc-
tures for the spokes of the
ʱ
-donutfor
e
ʱ
, a decision on whether some spoke is or is
not in
S
can be taken withoutlossofgenerality. We start with the following:
∈
∈
∈
↗
Lemma 14 (
S
IMPLIFICATION
5
).
Suppose thatspokes
e
i
ʱ
and
e
i
+
ʱ
haveisomorphic
conflicting structures. Then,there exists a planarset
S
of spanning trees for
A
if and
only if there exists a planarset
S
of spanning trees for
A
such that
e
i
ʱ
/
S
.
∈
Proof sketch.
Suppose that a planar set
S
of spanning trees for
A
exists with
e
i
ʱ
∈
S
.
By Lemma 5,
j
H
j
(
e
i
ʱ
)
∩
j
L
j
(
e
i
ʱ
)=
. By Lemma 13,
e
i
+1
ʱ
ↆ
S
and
S
∅
∈
/
S
,
hence
j
L
j
(
e
i
+
ʱ
)
∩
j
H
j
(
e
i
+
ʱ
)=
.Let
S
be the set of con-edges
obtained from
S
by removing
j
H
j
(
e
i
ʱ
) and
j
L
j
(
e
i
+
ʱ
) andbyadding
j
L
j
(
e
i
ʱ
)
ↆ
S
and
S
∅
and
j
H
j
(
e
i
+
ʱ
). The lemma follows from the claim that
S
is a planar set of spanning
trees for
A
. The proof for this claim consists of two parts. In the first one, it is shown
that no two con-edges in
S
cross, by exploiting the absence of crossingsin
S
and the
properties of
M
(
e
i
ʱ
) and
M
(
e
i
+
ʱ
). In the second one, it is shown that, for each cluster
μ
,thegraph induced by the con-edges in
S
[
μ
] is a tree that spans the vertices in
μ
;this
