Information Technology Reference
In-Depth Information
the cd-tree. The skeleton of
is a planar graph yielding (as in the flat-clustered case)
partitioned PQ-constraints for its parent
μ
μ
. This restricts the possible embeddingsof
μ
) and thus the order-constraints one obtains for the parent of
μ
are not neces-
skel(
sarily again partitioned PQ-constraints.
One can express this issue in the following, more formal way. Let
G
beaplanar
multi-graph with vertices
v
1
,...,
v
n
and designated vertex
v
=
v
n
.Themap
v
G
maps
atuple (
C
1
,...,
C
n
) where
C
i
is an order-constraint on the edges incident to
v
i
to an
order-constraint
C
on the edges incident to
v
. The order-constraint
C
=
˕
v
G
(
C
1
,...,
C
n
)
contains exactly those edge-orderingsof
v
that one can get in a planar embedding of
G
that respects
C
1
,...,
C
n
. Note that
C
is empty if and only if there is no such embed-
ding.Notefurther that testing planarity with order-constraints is equivalent to deciding
whether
˕
v
v
˕
G
evaluates to the empty set. We call such a map
˕
G
a
constrained-embedding
operation
.
The issue mentioned above (constraints iteratively handed to parents) boils down to
the fact that partitioned PQ-constraints are not closed under constrained-embedding op-
erations. On the positive side, we obtain a general algorithm for solving c-planarity as
follows. Assume we have a family of order-constraints
with compact representations
that is closed under constrained-embedding operations. Assume further that we can
evaluate the constrained embedding operations in polynomial time on order-constraints
in
C
. Then one can simply solve c-planarity by traversing the cd-tree bottom-up, eval-
uating for a node
C
˕
skel(μ)
μ
with parent vertex
ʽ
the constrained-embedding operation
on the constraints one computed in the same way for the children of
.
Clearly, when restricting the skeletons of the cd-tree or requiring properties for
the parent vertices in these skeletons, these restrictions carry over to the constrained-
embedding operations one has to consider. More precisely, let
μ
R
be a set of pairs (
G
,
v
),
where
v
is a vertex in
G
. We say that a clustered graph is
R
-restricted
if (skel(
μ
)
,
ʽ
)
∈R
holds for every node
μ
in the cd-tree with parent vertex
ʽ
. Moreover, the
R
-restricted
G
with (
G
,
v
)
constrained-embedding operations are those operations
˕
∈R
.Thefol-
lowing theorem directly follows.
Theorem 3.
Onecan solvec-planarity of
R
-restricted clustered graphsin polynomial
timeifthere is a family
C
of order-constraints such that
-
C
has a compact representation,
-
C
is closed under
R
-restricted constrained-embedding operations,
R
C
-
every
-restricted constrained-embedding operation on order-constraints in
can
be evaluated in polynomialtime.
has a compact representation the algorithm
becomes super-polynomial only in the maximumdegree
d
of the virtual vertices (the
number of possible order-constraints for a set of size
d
depends only on
d
). Moreover,
if
When dropping the requirement that
C
G
has only
k
order constraints (whose sizes are bounded by a function of
d
)as
input, then
˕
G
can be evaluated by iterating over all combinations of orders, applying a
planarity test in every step. This gives an FPT- a lgorithm with parameter
d
+
k
(running
time
O
(
f
(
d
+
k
)
p
(
n
)),where
f
is a computable function depending only on
d
+
k
and
p
is a polynomial). In other words, we obtain an FPT- a lgorithm where the parameter is the
sum of the maximumdegree of the tree
T
and the maximumnumber of edges leaving
˕
