Information Technology Reference
In-Depth Information
of the skeletons, the edge-ordering of a virtual vertex and its twin is the same upto
reversal. To make them the same one can choose a 2-coloring of
T
and mirror the
embeddings of all skeletons of nodes in one color class.
Conversely, assume that all skeletons are embedded such that every virtual vertex and
its twin have the same edge-ordering.Let
μ
be a node of
T
. Consider a virtual vertex
ʽ
i
1
of skel(
μ
) with edge-ordering
e
1
,...,
e
. We replace
ʽ
i
by a cycle
C
i
=(
ʽ
i
,...,
ʽ
i
) and
j
i
;seeFig. 1c. Recall that twin(
attach the edge
e
j
to the vertex
ʽ
ʽ
i
) has in skel(
μ
i
) the
same incident edges
e
1
,...,
e
appearing in this order around twin(
ʽ
i
). We also replace
twin(
ʽ
i
) by a cycle of length
. This cycle is the
twin
of
C
i
anddenoteitbytwin(
C
i
)=
(twin(
j
i
) denotes the new vertex incident to the edge
e
j
. As the interiors of
C
i
and twin(
C
i
) are empty, we can glue the skeletons skel(
i
)
,...,
twin(
i
)) where twin(
ʽ
ʽ
ʽ
μ
) and
skel(twin(
)) together by identifying the vertices of
C
i
with the corresponding vertices
in twin(
C
i
) (one of the embeddings has to be flipped). Applying this replacement for
every virtual vertex and gluing it with its twin leads to an embedded planar graph
G
+
with the following properties. First,
G
+
contains a subdivision of
G
. Second, for every
cut corresponding to an edge
μ
in
T
,
G
+
contains the cycle
C
i
with exactly
one subdivision vertex of an edge
e
of
G
if the cut corresponding to
ʵ
=
{
μ
,
μ
i
}
separates the
endpoints of
e
. Third, no two of these cycles share a vertex. The planar drawing of
G
+
gives a planar drawing of
G
.Moreover,thedrawings of the cycles can be used as curves
representing the cuts, yielding a c-planar drawing of
G
.
ʵ
Cutvertices in Skeletons.
We s h ow t h a t cutvertices in skeletons correspond to different
connected components in a cluster or in a co-cluster.
Lemma 1.
Let
be avirtual vertex thatisa cutvertex in its skeleton.Theexpansion
graphsofvirtual vertices in differentblocksincidentto
ʽ
ʽ
belong to differentconnected
components in
exp(twin(
ʽ
))
.
Proof.
Let
μ
be the node whose skeleton contains
ʽ
. Recall that one can obtain the
graph exp(twin(ʽ)) by removing
ʽ
from skel(μ) and replacing all other virtual vertices
of skel(
) with their expansion graphs. Clearly, this yields (at least) one connected
component for each of the blocks incident to
μ
ʽ
.
Lemma 2.
Every cluster inaclustered graph is connected if andonly if in everynode
μ
of the rooted cd-tree theparent vertex is not a cutvertex in
skel(
μ
)
.
Proof.
By Lemma 1, the existence of a cutvertex implies a disconnected cluster. Con-
versely, let pert(
μ
) be disconnected and assume withoutlossofgenerality that pert(
μ
i
)
is connected for every child
μ
1
,...,
μ
k
of
μ
in the cd-tree. One obtains skel(
μ
) without
the parent vertex
ʽ
by contracting in pert(
μ
) the child clusters pert(
μ
i
) to virtual ver-
tices
ʽ
i
. As the contracted graphs pert(
μ
i
) are connected while the initial graph pert(
μ
)
is not, the resultinggraph must be disconnected. Thus,
ʽ
is a cutvertex in skel(
μ
).
4
Clustered and Constrained Planarity
We first describe several constraints on planar embeddings, each restricting the edge-
orderings of vertices. We then show the relation to c-planarity.
