Information Technology Reference
In-Depth Information
(see [11]); hence, testing the
c
-planarity of
C
is equivalent to solve the
PSSTTM
problem
for
A
. Finally, as described before the lemma, there exists an
O
(
|
C
|
2
)-time algorithm
that modifies multigraph
A
so that it satisfies Property 1.
3
Algorithm Outline
In this section we give an outline of ouralgorithm for testing the existence of a planar
set
S
of spanning trees for
A
.Weassume that
A
satisfies Property 1.
Ouralgorithm repeatedly tries to detect certain substructures in
A
. When it does
find one of such substructures, the algorithm either “simplifies”
A
or concludes that
A
does not admit any planar set of spanning trees. For example, if a cluster
ʱ
exists such
that
A
[
ʱ
] is not connected, then the algorithm concludes that no planar set of spanning
trees exists and terminates; as another example, if conflicting con-edges
e
ʱ
and
e
ʲ
for clusters
ʱ
and
ʲ
exist in
A
such that
e
ʱ
is a bridgefor
A
[
ʱ
], then the algorithm
determines that
e
ʱ
has to be in
S
and that
e
ʲ
can be assumed not to be in
S
.
If the algorithm determines that certain edges have to be in
S
or can be assumed not
to be in
S
,theseedges are contracted or removed, respectively. Given a set
A
ↆ
A
,
the operation of
removing
A
from
A
consists of updating
A
:=
A
A
. Given a set
\
A
ↆ
A
, the operation of
contracting
the edges in
A
consists of identifying the end-
vertices of each con-edge
e
in
A
(all the con-edges different from
e
and incident to the
end-vertices of
e
remain in
A
), and of updating
A
:=
A
A
.
Edges are removed or contracted only when this does not alter the possibility of
finding a planar set of spanning trees for
A
. Also, contractions are only applied to
con-edges that cross no other con-edges; hence, after any contraction, graph
K
A
only
changes for the removal of the isolated vertices corresponding to the contracted edges.
As a consequence of a removal or of a contraction operation, the number of edges
in
A
decreases, that is,
A
is “simplified”. After any simplification due to the detection
of a certain substructure in
A
,thealgorithm will runagain all previoustestsforthe
detection of the other substructures. In fact, it is possible that a certain substructure
arises from performing a simplification on
A
(e.g., a bridgemight be present in
A
after
a set of edges has been removed from
A
). Since detecting each substructure that leads
to a simplification in
A
can be performed in quadratic time, and since the initial size of
A
is linear in the size of
C
,thealgorithm has a cubic running time.
If none of the four tests (called T
EST
1-4) and none of the eight simplifications
(called S
IMPLIFICATION
1-8) described in Section 4 applies to
A
,then
A
is a
single-
conflict
multigraph. That is, each con-edgein
A
crosses at most one con-edgein
A
.
A linear-time algorithm for deciding the existence of a planar set of spanning trees
in a single-conflict multigraph
A
is known [11]. Hence, ouralgorithm uses that algo-
rithm [11] to conclude the test of the existence of a planar set of spanning trees in
A
.
\
4
Algorithm
To ease the reading and avoid text duplication, when introducing a new lemma we al-
ways assume, withoutmaking it explicit, that all the previously defined simplifications
