Information Technology Reference
In-Depth Information
(a)
(b)
(c)
(d)
Fig. 1.
(a) A clustered graph
C
. (b) Con-edges in
C
.(c)Multigraph
A
. (d) A planar set
S
of
spanning trees for
A
.Edges in
S
are thick and solid, while edges in
A \ S
are thin and dashed.
becomes seemingly simpler. Since the embedding of
G
is fixed and since
G
has to
be planar, edges in
S
can only be embedded inside faces of
G
. This implies that, for
any two edges
e
1
and
e
2
that can be inserted inside a face
f
of
G
, it is known
a priori
whether
e
1
and
e
2
can be both in
S
, namely only if their end-vertices do not alternate
along the boundary of
f
.Also,
S
can be assumed to contain only edges between vertices
in distinct connected components of
G
[
ʱ
], for each cluster
ʱ
,asothertypesofedges
do not help to connect any cluster.
Consider a face
f
of
G
and let (
o
1
,...,o
k
) be the clockwise order of the occur-
rences of vertices along the boundary of
f
,where
o
i
and
o
j
might be occurrences of
thesamevertex
u
(this might happen if
u
is a cut-vertex of
G
). A
con-edge
(short for
connectivity-edge
) is a pair of occurrences (
o
i
,o
j
) of distinct vertices both belonging
to a cluster
ʱ
, both incident to
f
, and belonging to different connected components of
G
[
ʱ
] (see Fig. 1(b)). If there are
distinct pairs of occurrences of vertices
u
and
v
along
asingle face
f
, then there are
con-edges connecting
u
and
v
in
f
, one for each pair
of occurrences. A
con-edgefor
ʱ
is a con-edge connecting vertices in a cluster
ʱ
.Two
con-edges
e
and
e
in
f
have a conflict
or
cross
(we write
e
e
) if the occurrences in
↗
e
alternate with the occurrences in
e
along the boundary of
f
.
The
multigraph
A
of thecon-edges
is an embedded multigraph that is defined as
follows. Starting from
G
, insert all the con-edges inside the faces of
G
; then, for each
cluster
ʱ
and for each connected component
G
i
[
ʱ
] of
G
[
ʱ
], contract
G
i
[
ʱ
] into a single
vertex; finally, remove all the edges of
G
.SeeFig. 1(c). With a slight abuse of notation,
we denote by
A
both the multigraph of the con-edges and the set of its edges. For each
cluster
ʱ
, we denote by
A
[
ʱ
] the subgraph of
A
induced by the con-edges for
ʱ
.A
planarsetofspanning trees for
A
is a set
S
A
such that: (i) for each cluster
ʱ
,
the subset
S
[
ʱ
] of
S
induced by the con-edges for
ʱ
is a tree that spans the vertices
belonging to
ʱ
; and (ii) there exist no two edges in
S
that have a conflict. See Fig. 1(d).
The
PSSTTM
problem asks whether a planar set of spanning trees for
A
exists.
The following lemma relates the
c
-planarity problem for embedded flat clustered
graphs to the
PSSTTM
problem.
ↆ
Lemma 1 ( [11]).
An embedded flatclustered graph
C
(
G, T
)
is
c
-planarifandonly if:
(1)
G
is planar; (2) there exists a face
f
in
G
such that when
f
is chosenasouter face
for
G
nocycle composed of vertices of thesamecluster encloses avertex of a different
cluster; and(3)a planarsetofspanning trees for
A
exists.
