Information Technology Reference
In-Depth Information
do not apply, and that all the previously defined tests fail. Also, we do not make explicit
the removal and contraction operations that we perform, as they straight-forwardly fol-
low from the statement of each lemma. We start with the following test.
Lemma 3 (
T
EST
1
).
Let
ʱ
be a cluster such that
A
[
ʱ
]
is disconnected. Then,there
exists noplanarset
S
of spanning trees for
A
.
Proof.
No set
S ↆ A
is such that
S
[
ʱ
] induces a tree spanning the vertices in
ʱ
.
We continue with the following simplification.
Lemma 4 (
S
IMPLIFICATION
1
).
Let
e
be a bridgeof
A
[
ʱ
]
.Then,forevery planarset
S
of spanning trees for
A
, we have
e
∈
S
.
is disconnected; hence, by Lemma 3, no planar set of
spanning trees for
A
exists with
e/
Proof.
Graph
A
[
ʱ
]
\{
e
}
∈
S
.
The following lemma is used massively in the remainder of the paper.
Lemma 5.
Let
e
ʱ
,e
ʲ
∈
A
be con-edges such that
e
ʱ
↗
e
ʲ
.Let
S
be a planarsetof
spanning trees for
A
andsuppose that
e
ʱ
/
∈
S
.Then,
e
ʲ
∈
S
.
Proof sketch.
If
S
contains neither
e
ʱ
nor
e
ʲ
, then the two paths in
S
connecting the
end-vertices of
e
ʱ
and connecting the end-vertices of
e
ʲ
cross, a contradiction.
The algorithm continues with the following test.
Lemma 6 (
T
EST
2
).
If theconflict graph
K
A
is not bipartite, then there exists nopla-
narset
S
of spanning trees for
A
.
exists in
K
A
, then by repeated applications of
Lemma 5 and of the fact that
S
does not contain two conflicting edges, we get that
any edgeof
Proof sketch.
If an odd cycle
C
The contraction of con-edges chosen to be in
S
might lead to self-loops in
A
,a
situation that is handled in the following.
C
simultaneously should be in
S
and should not be in
S
, a contradiction.
Lemma 7 (
S
IMPLIFICATION
2
).
Let
e
∈
A
be a self-loop. Then,forevery planarset
S
of spanning trees for
A
, we have
e/
∈
S
.
Proof.
Since a tree does not contain any self-loop, the lemma follows.
Con-edges that do not cross any other con-edge can be safely chosen to be in
S
.
Lemma 8 (
S
IMPLIFICATION
3
).
Let
e
be any con-edgein
A
that does not have a con-
flict with any other con-edgein
A
.Then,there exists a planarset
S
of spanning trees
for
A
if andonly if there exists a planarset
S
of spanning trees for
A
such that
e
S
.
∈
Proof sketch.
Let
S
be any planar set of spanning trees for
A
.If
e/
∈
S
,then
S
∪{
e
}
of con-edges for the same cluster. Let
e
be any edgeof
contains a cycle
C
C
different
from
e
. Then,
S
=
S
e
}
∪{
e
}\{
is a planar set of spanning trees for
A
.
