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(
μ
).
 
Search WWH ::




Custom Search