Information Technology Reference
In-Depth Information
b
(a)
(b)
b
(c)
d
d
e
b
b
d
b
1
b
d
4
h
4
h
d
4
1
g
d
e
b
a
1
f
a
a
g
f
2
c
f
d
5
h
g
h
5
2
3
c
e
3
2
e
5
g
c
g
h
g
h
e
3
e
h
6
6
6
g
i
i
i
e
7
8
e
h
i
78
e
h
i
7
8
Fig. 1.
(a) A c-planar drawing of a clustered graph. (b) The corresponding (rooted) cd-tree (with-
out leaves). The skeletons are drawn inside their corresponding (gray) nodes. Every pair of twins
has the same edge-ordering. (c) Construction of a c-planar drawing from the cd-tree.
The leaves of a cd-tree represent singleton clusters that exist only due to technical
reasons. It is often more convenient to consider cd-trees with all leaves removed as
follows. Let
μ
be a node with virtual vertex
ʽ
in skel(
μ
) that corresponds to a leaf.
The leaf contains twin(
ʽ
) and a non-virtual vertex
v
∈
V
in its skeleton (with an edge
between twin(
)
with the non-virtual vertex
v
and remove the leaf containing
v
. Clearly, this preserves
all clusters except for the singleton cluster. Moreover, the graph
G
represented by the
cd-tree remains unchanged as we replaced the virtual vertex
ʽ
) and
v
for each edgeincidentto
v
in
G
). We replace
ʽ
in skel(
μ
ʽ
by its expansion graph
exp(
ʽ
)=
v
. In the following we always assume the leaves of cd-trees to be removed.
The CD-Tree Characterization.
We show that c-planarity testing can be expressed in
terms of edge-orderings in embeddings of the skeletons of
T
.
Theorem 1.
Aclustered graph is c-planarifandonly if theskeletonsofall nodes in
its cd-tree can be embedded such thateveryvirtual vertex and its twin havethesame
edge-ordering.
Proof.
Assume
G
admits a c-planar drawing
ʓ
on the sphere. Let
μ
be a node of
T
with incident edges
ʵ
1
,...,
ʵ
k
connecting
μ
to its neighbors
μ
1
,...,
μ
k
, respectively. Let
further
ʽ
i
be the virtual vertex in skel(
μ
) corresponding to
μ
i
and let
V
i
be the nodes
ʽ
i
).Foreverycut (
V
i
,
V
i
) (with
V
i
=
V
in the expansion graph exp(
contains a
simple closed curve
C
i
representing it. Since the
V
i
are disjoint, we can choose a point
on the sphere to be the outside such that
V
i
lies inside
C
i
for
i
= 1
,...,
k
.Since
\
V
i
),
ʓ
is a c-
planar drawing,the
C
i
do not intersect and only the edges of
G
crossing the cut (
V
i
,
V
i
)
cross
C
i
exactly once. Thus, one can contract the inside of
C
i
to a single point while
preserving the embedding of
G
.Doing this for each of the curves
C
i
yields skel(
ʓ
μ
)
together with a planar embedding. Moreover, the edge-ordering of
ʽ
i
is the same as
the order in which the edges cross the curve
C
i
. Applying the same construction for
the neighbor
μ
i
corresponding to
ʽ
i
yields a planar embedding of skel(
μ
i
) in which the
ʽ
i
) is the same as the order in which these edges cross the curve
C
i
, when traversing
C
i
in counter-clockwise direction. Thus, in the resulting embeddings
edge-ordering of twin(
