Information Technology Reference
In-Depth Information
μ
G
μ
i
b
twin(
ʽ
i
)
b
c
c
b
a
a
d
d
c
a
d
f
f
e
e
e
f
ʽ
i
Fig. 2.
A graph
G
with a single cluster consisting of isolated vertices together with an illustration
of its cd-tree. An edge-ordering of twin(ʽ
i
) corresponds to a planar embedding of skel(μ
i
) if and
only if no two partitions of
{{
a
,
b
}
,
{
c
,
d
,
f
}
,
{
e
}}
alternate.
edges) to the virtual vertex twin(
ʽ
i
). The vertices
v
1
,...,
v
partition the edges incident
to twin(
ʽ
i
) into
subsets. Clearly, in every planar embedding of skel(
μ
i
) no two par-
titions alternate. Moreover, every edge-ordering of twin(
ʽ
i
) in which no two partitions
alternate gives a planar embedding of skel(
)
are constrained by a partition-constraint, where the partitions are determined by the in-
cidence of the edges to the vertices
v
1
,...,
v
. One can easily construct the resulting
instance of planarity with partition-constraints problem in linear time in the size of the
cd-tree, which is linear in the size of
G
for flat-clustered graphs.
Conversely, given a planar graph
H
with partition-constraints, we set skel(
μ
i
).Thus, the edges incident to
ʽ
i
in skel(
μ
μ
)=
H
.
For every vertex of
H
we have a virtual vertex
ʽ
i
in skel(
μ
) with corresponding child
μ
i
.
We can simulate every partitioning of the edges incident to
ʽ
i
by connecting edges
incident to twin(
μ
i
)) with vertices such that two edges are connected with
the same vertex if and only if they belong to the same partition.
Consider case (ii). By Lemma 2 the condition of connected clusters is equivalent to
requiring that the virtual vertex twin(
ʽ
i
) (in skel(
μ
i
of the cd-tree is
not a cutvertex. The statement follows from the fact that the possible edge-orderingsof
non-cutvertices is PQ-representable and that any PQ-tree can be achieved by choosing
an appropriate planar graph in which twin(
ʽ
i
) in the skeleton of any leaf
ʽ
i
) is not a cutvertex (see Sec. 2).
Consider case (iii). As in case (i), the blocks incident to twin(
ʽ
i
) in skel(
μ
i
) partition
the edges incident to
) such that two partitions must not alternate. The
fixed embedding of
G
fixes the edge-ordering of non-virtual vertices and thusfixesthe
embeddings of the blocks in skel(
ʽ
i
in skel(
μ
μ
i
). Hence, we get partitioned full-constraints for
ʽ
i
.
Conversely, we can construct an arbitrary partitioned full-constraint as in case (i).
For case (iv) the arguments from case (iii) show that we again get partitioned order-
constraints, while the arguments from case (ii) show that these order-constraints (for
the blocks) are PQ-constraints.
Related Work.
Biedl [1] proposes different drawing-models for graphs whose vertices
are partitioned into two subsets. The model matching the requirements of c-planar draw-
ingsiscalled
HH-drawings
. Biedl et al. [2] show that one can test for the existence of
HH-drawings in linear time. Hong and Nagamochi [16] rediscovered this result in the
context of 2-page topic embeddings. These results solve c-planarity for flat-clustered
graphs if the skeleton of the root node contains two virtual vertices. This is equiva-
lent to testing planarity with partitioned PQ-constraints for multi-graphs with only two
