Information Technology Reference
In-Depth Information
(i) Every region
R
μ
. (ii) Two regions have
non-empty intersection only if one contains the other. (iii) Edges cross the boundary of
aregion at most once. A clustered graph is
c-planar
if it admits a c-planar drawing.
This definition relies on embeddings in the plane using terms like “outside” and
“inside”. Instead, one can consider drawings on the sphere by unrooting
T
, using cuts
instead of clusters and simple closed curves instead of simple regions. Removing an
edge
contains exactly the vertices of the cluster
μ
of
T
splits
T
in two components. As the leaves of
T
are the vertices of
G
,this
induces a
corresponding cut
(
V
ʵ
,
V
ʵ
) with
V
ʵ
on
G
. For a c-planar drawing of
G
on the sphere, we require a planar drawing of
G
together with a simple closed curve
C
=
V
\
V
ʵ
ʵ
,
V
ʵ
for every cut (
V
) with the following properties. (i) The curve
C
ʵ
separates
V
ʵ
ʵ
ʵ
from
V
ʵ
at most once.
Using clusters instead of cuts corresponds to orienting the cuts, using one side as
cluster and the other side as the cluster's complement (
co-cluster
). C-planarity on the
sphere and in the plane are equivalent; one simply has to choose an appropriate point on
the sphere to lie in the outer face. We use the rooted and unrooted view interchangeably.
. (ii) No two curves intersect. (iii) Edges of
G
cross
C
ʵ
3
The CD-Tree
The
cd-tree (cut- or cluster-decomposition-tree)
of a clustered graph (
G
,
T
) is the tree
T
together with a multi-graph associated with each node of
T
that represents the decompo-
sition of
G
along its cuts corresponding to edges in
T
;seeFig. 1a and b for an example.
Lengauer [21] uses a similar structure. Our notation is inspired by SPQR-trees.
Let
μ
be a node of
T
with neighbors
μ
1
,...,
μ
k
and incident edges
ʵ
i
=
{
μ
,
μ
i
}
.
Removing
separates the leaves of
T
into
k
subsets and thus partitions the vertices
of
G
into
V
1
,...,
V
k
ↆ
μ
is the multi-graph obtained from
G
by contracting each subset
V
i
into a
virtual vertex
V
.The
skeleton
skel(
μ
) of
μ
ʽ
i
(we keep multiple edges but
remove loops). Note that skeletons of inner nodes of
T
contain only virtual vertices,
while skeletons of leaves consist of one virtual and one non-virtual vertex. The node
μ
i
is the neighbor of
μ
corresponding
to
ʽ
i
and the virtual vertex in skel(μ
i
) corresponding
to
μ
ʽ
i
, denoted by twin(ʽ
i
). Note that twin(twin(ʽ
i
)) = ʽ
i
.
The edges incident to
is the
twin
of
ʽ
i
are exactly the edges of
G
crossing the cut corresponding to
thetreeedge
ʽ
i
).Thisgives a
bound on the total size
c
of the cd-tree's skeletons (which we shortly call the
size of the
cd-tree
). The total number of edges in skeletons of
T
is twice the total size of all cuts
represented by
T
.Since
T
represents
O
(
n
) cuts, each of size
O
(
n
),itis
c
ʵ
i
.Thus, the same edges of
G
are incident to
ʽ
i
and twin(
O
(
n
2
).
∈
Assume the cd-tree is rooted. Recall that in this case every node
μ
represents a
cluster of
G
.The
pertinent graph
pert(
.
Note that one could also define the pertinent graph recursively, by removing the virtual
vertex corresponding to the parent of
μ
) of the node
μ
is the cluster represented by
μ
) and replacing
each remaining virtual vertex by the pertinent graph of the corresponding child of
μ
(the
parent vertex
) from skel(
μ
.
Clearly, the pertinent graph of a leaf of
T
is a single vertex and the pertinent graph of
the root is the whole graph
G
. A similar concept, also defined for unrooted cd-trees,
is the
expansiongraph
. The expansion graph exp(
μ
ʽ
i
) of a virtual vertex
ʽ
i
in skel(
μ
) is
the pertinent graph of its corresponding neighbor
μ
i
of
μ
, when rooting
T
at
μ
. One can
think of the expansion graph exp(
ʽ
i
) as the subgraph of
G
represented by
ʽ
i
in skel(
μ
).