Information Technology Reference
In-Depth Information
acluster. Note that this generalizes the FPT- a lgorithm by Chimani and Klein [6] with
respect to the total number of edges connecting different clusters.
Moreover, Theorem 3 has the following simple implication. Consider a clustered
graph where each cluster is connected. This restricts the skeletons of the cd-tree such
that none of the parent vertices is a cutvertex (Lemma 1). Thus, we have
R
-restricted
clustered graphs where (
G
,
v
)
∈R
implies that
v
is not a cutvertex in
G
. PQ-constraints
are closed under
-restricted constrained-embedding operations as the valid edge-
ordering of non-cutvertices is PQ-representable and planarity with PQ-constraints is
basically equivalent to planarity (one can model a PQ-tree with a simple gadget; see
Sec. 2). Thus, Theorem 3 directly implies that c-planarity can be solved in polynomial
time if each cluster is connected.
R
Related Work.
The above algorithm resulting from Theorem 3 is more or less the one
described by Lengauer [21]. The algorithm was later rediscovered by Feng et al. [13]
who coined the term “c-planarity”. The algorithm runs in
O
(
c
)
O
(
n
2
) time (recall that
c
is the size of the cd-tree). Dahlhaus [11] improves the running time to
O
(
n
).Cortese
et al. [8] give a characterization that also leads to a linear-time algorithm.
Goodrich et al. [14] consider the case where each cluster is either connected or
ex-
trovert
.Let
ↆ
μ
.Thecluster pert(
μ
be a node in the cd-tree with parent
μ
) is extrovert
μ
) is connected and every connected component in pert(
if the parent cluster pert(
μ
) is
μ
). They show that one obtains an equiv-
alent instance by replacing the extrovert cluster pert(
connected to a vertex not in the parent pert(
) with one cluster for each of its
connected components while requiring additional PQ-constraints for the parent vertex
in the resulting skeleton. In this instance every cluster is connected and the additional
PQ-constraints clearly do no harm.
Another extension to the case where every cluster must be connected is given by
Gutwenger et al. [15]. They give an algorithm for the case where every cluster is con-
nected with the following exception. Either, the disconnected clusters form a path in
the tree or for every disconnected cluster the parent and all siblings are connected. This
has basically the effect that at most one order-constraint in the input of a constrained-
embedding operation is not a PQ-tree.
Jelínek et al. [17, 18] assume each cluster to have at most two connected compo-
nents and the underlying (connected) graph to have a fixed planar embedding.Thus,
they consider
μ
implies that
v
is incident
to at most two different blocks. The fixed embedding of the graph yields additional
restrictions that are not so easy to state within this model.
R
-restricted clustered graphs where (
G
,
v
)
∈R
5
Cutvertices with Two Non-trivial Blocks
The inputoftheS
IMULTANEOUS
PQ-O
RDERING
problem consists of several PQ-trees
together with child-parent relations between them (the PQ-trees are the nodes of a di-
rected acyclic graph) such that the leaves of every child form a subset of the leaves of
its parents. S
IMULTANEOUS
PQ-O
RDERING
asks whether one can choose orders for
all PQ-trees
simultaneously
in the sense that every child-parent relation implies that the
order of the leaves of the parent are an extension of the order of the leaves of the child.
