Information Technology Reference
In-Depth Information
In this way one can represent orders that cannot be represented by a single PQ-tree. For
example, adding one or more children to a PQ-tree
T
restricts the set of orders repre-
sented by
T
by requiring the orders of different subsets of leaves to be represented by
some other PQ-tree. Moreover, one can synchronize the orders of different trees that
shareasubset of leaves by introducing a common child containing these leaves.
S
IMULTANEOUS
PQ-O
RDERING
is NP-hard but efficiently solvable for so-called
2-fixed instances [4]. For every biconnected planar graph
G
, there exists an instance
of S
IMULTANEOUS
PQ-O
RDERING
,the
PQ-embedding representation
, that represents
all planar embeddingsof
G
[4]. It has the following properties.
-
For every vertex
v
in
G
there is a PQ-tree
T
(
v
),the
embedding tree
,thathasthe
edges incident to
v
as leaves.
-
For every solution of the PQ-embedding representation, setting the edge-ordering
of every vertex
v
to the order given by
T
(
v
) yields a planar embedding. Moreover,
one can obtain every embedding of
G
in this way.
-
The instance remains 2-fixed when addingup to one child to each embedding tree.
A PQ-embedding representation still exists if every cutvertex in
G
is incident to at most
two
non-trivialblocks
(blocks that are not just bridges) [3].
Theorem 4.
C-planarity can be tested in O
(
c
2
)
ↆ
O
(
n
4
)
timeifeveryvirtual vertex in
theskeletonsofthe cd-tree is incidenttoat most two non-trivialblocks.
Proof.
Let
G
be a clustered graph with cd-tree
T
. For the skeleton of each node in
T
,
we get a PQ-embedding representation with the above-mentioned properties. Let
μ
be
μ
be the node whose skeleton
a node of
T
and let
ʽ
be a virtual vertex in skel(μ).Let
μ
) contain the
contains twin(
ʽ
). The embedding representations of skel(
μ
) and skel(
embedding trees
T
(
ʽ
) and
T
(twin(
ʽ
)) representing the edge-orderingsof
ʽ
and twin(
ʽ
),
respectively. To ensure that
ʽ
and twin(
ʽ
) havethesameedge-ordering, one can simply
add a PQ-tree as common child of
T
(
)). We do this for every virtual
node in the skeletons of
T
.Due to the last property of the PQ-embedding representations,
the resulting instance remains 2-fixed and can thus be solved efficiently.
Every solution of this S
IMULTANEOUS
PQ-O
RDERING
instance
D
yields planar
embeddings of the skeletons such that every virtual vertex and its twin have the same
edge-ordering and vice versa. By Theorem 1, testing c-planarity is equivalent to solving
D
. The size of
D
is linear in the size
c
of
T
. Moreover, solving S
IMULTANEOUS
PQ-
O
RDERING
for 2-fixed instances can be done in quadratic time [4], yielding the running
time
O
(
c
2
).
ʽ
) and
T
(twin(
ʽ
Theorem 4 includes the following interesting cases. The latter extends the result by
Jelínek et al. [19] from fourtofiveoutgoing edges per cluster.
Corollary 1.
C-planarity can be tested in O
(
c
2
)
O
(
n
4
)
timeifevery cluster andevery
ↆ
co-cluster has at most twoconnected components.
Corollary 2.
C-planarity can be tested in O
(
n
2
)
timeifevery cluster has at most five
outgoing edges.
