Information Technology Reference
In-Depth Information
of testing whether a given cl-graph is cl-planar. This problem was introduced by Forster
and Bachmaier [9], who showed a polynomial-time testing algorithm for the case in
which the level graph is a proper hierarchy and the clusters are level-connected.
A
T
-level graph
(also known as
generalized
k
-ary tanglegram
) (
V,E,ʳ,
T
) is a
level graph (
V,E,ʳ
) equipped with a set
=
T
1
,...,T
k
of trees such that the leaves
of
T
i
are the vertices of level
V
i
of (
V,E,ʳ
),for1
T
≤
i
≤
k
.A
T
-level planardrawing
of (
V,E,ʳ,
) is a level planar drawing of (
V,E,ʳ
) such that, for
i
=1
,...,k
,the
order in which the vertices of
V
i
appear along
L
i
is
compatible
with
T
i
, that is, for each
node
w
of
T
i
, the leaves of the subtree of
T
i
rooted at
w
appear consecutively along
L
i
.A
T
T
-level graph is
T
-level planar
if it admits a
T
-level planar drawing.
T
-L
EVEL
P
LANARITY
is the problem of testing whether a given
-level planar.
This problem was introduced by Wotzlaw
et al.
[13], who showed a quadratic-time
algorithm for the case in which the level graph is proper and the number of vertices of
each level is bounded by a constant.
The definition of
proper
naturally extends to cl-graphs and
T
-level graph is
T
-level graphs. Note that,
given any non-proper level graph
G
it is easy to construct a proper level graph
G
that is
level planar if and only if
G
is level planar. However, as mentioned above, there exists
no trivial transformation from a non-proper cl-graph (a non-proper
T
T
-level graph) to an
equivalent proper cl-graph (resp., an equivalent proper
-level graph).
In this paper we show that C
LUSTERED
-L
EVEL
P
LANARITY
and
T
-L
EVEL
P
LA
-
NARITY
are
T
-complete for non-proper instances. Conversely, we show that both
problems are polynomial-time solvable for proper instances. Ourresults have several
consequences: (1) They narrow the gap between polynomiality and
NP
-completeness
in the classification of Schaefer [12] (see Fig.1).Thereduction of Schaefer between
T
-L
EVEL
P
LANARITY
and SEFE-2 holds for proper instances [12]. (2) They allow
to partially answer a question from [12] asking whether a reduction exists from CL-
P
LANARITY
to SEFE-2. We show that such a reduction exists for proper instances and
that a reduction from general instances would imply the
NP
-hardness of SEFE-2.(3)
They improve on [9] and [13] by extending the classes of instances which are decidable
in polynomial-time for CL-P
LANARITY
and
T
-L
EVEL
P
LANARITY
, respectively. (4)
They provide the first, as far as we know,
NP
-completeness for a problem that has all
the constraints of the clustered planarity problem (and some more).
The paper is organized as follows. The
NP
-completeness proofs are in Section 2,
while the algorithms are in Section 3. We conclude with open problems in Section 4.
NP
2 NP-Hardness
In this section we prove that the
T
-L
EVEL
P
LANARITY
and the CL-P
LANARITY
prob-
lems are
NP
-complete. In both cases, the
NP
-hardness is proved by means of a
polynomial-time reduction from the
-complete problem B
ETWEENNESS
[11], that
takes as input a finite set
A
of
n
objects and a set
C
of
m
ordered triples of distinct
elements of
A
, and asks whether a linear ordering
NP
O
of the elements of
A
exists such
that for each triple
ʱ, ʲ, ʴ
of
C
, we have either
O
=
<...,ʱ,...,ʲ,...,ʴ,...>
or
O
=
<...,ʴ,...,ʲ,...,ʱ,...>
.
