Information Technology Reference
In-Depth Information
u
ˁ
o
1
o
j
u
ˁ
u
ˁ
o
1
o
j
u
ˁ
x
y
x
y
o
p
o
q
o
p
o
q
f
f
f
f
o
o
v
ˁ
v
ˁ
v
ˁ
v
ˁ
(a)
(b)
(c)
(d)
Fig. 2.
Illustration for the reduction to a multigraph of the con-edges satisfyingProperty 1
We now introduce the concept of
conflict graph
K
A
, which is defined as follows.
Graph
K
A
has a vertex for each con-edgein
A
and has an edge (
e,e
) if
e
e
.Inthe
remainder of the paper we will show how to decide whether a set of planar spanning
trees for
A
exists by assuming that the following property holds for
A
.
↗
Property 1.
No twocon-edges for thesamecluster belong to thesameconnected com-
ponentof
K
A
.
We now show that
A
can be assumedtosatisfyProperty 1, since
C
(
G, T
) has at
most two vertices per cluster on each face. Consider any face
f
of
G
and any cluster
that has two vertices
u
and
v
incident to
f
. No con-edgefor
that connects a pair
of vertices different from (
u
,v
) is in the connected component of
K
A
containing
(
u
,v
), given that no vertex of
different from
u
and
v
is incident to
f
.However,it
might be the case that several con-edges (
u
,v
) are in the same connected component
of
K
A
, which happens if
u
,or
v
, or both have several occurrences on the boundary
of
f
.Weshowasimplereduction that gets rid of these multiple con-edges.
Let (
o
1
,...,o
k
) be the clockwise order of the occurrences of vertices along
f
.Let
o
1
,
o
j
,and
o
be occurrences of
u
,
u
,and
v
, respectively, with 1
<j<≤ k
.
Suppose that
o
p
and
o
q
are occurrences of vertices
x
and
y
in a cluster
˄
=
,forsome
1
<p<j<q<
,asinFig. 2(a). Then, all the con-edges (
x, y
) have a conflict with
con-edge
e
=(
o
j
,o
); moreover, the con-edges (
x, y
) form a separating set for
A
[
˄
],
hence any planar set
S
of spanning trees for
A
contains one of them. Thus,
e
/
S
and
e
can be removed from
A
,asinFig. 2(b). Similar reductions can be performed if
<q
∈
k
andbyexchanging the roles of
u
and
v
.Ifnotwooccurrences
o
p
and
o
q
as above exist, then all the con-edges (
u
,v
) left cross the same set of con-edges for
clusters different from
(see Fig. 2(c)). Hence, a single edge (
u
,v
) can be kept in
A
, and all the other con-edges (
u
,v
) can be removed from
A
(see Fig. 2(d)). After
repeating this reduction for all the con-edges in
A
,anequivalent instance
A
is eventually
obtained in which Property 1 is satisfied. Observe that the described simplification can
be easily performed in
O
(
≤
2
) time. Thus, we get the following:
|
C
|
Lemma 2.
Assumethatthe
PSSTTM
problem can be solved in
f
(
)
timeforinstances
satisfying Property 1. Then the
c
-planarity of any embedded flatclustered graph
C
with
at most two vertices per cluster on each face can be tested in
O
(
f
(
|
A
|
2
)
time.
|
A
|
)+
|
C
|
Proof.
Consider any embedded flat clustered graph
C
with at most two vertices per
cluster on each face. Conditions (1) and (2) in Lemma 1 can be tested in
O
(
|
C
|
) time
