Information Technology Reference
In-Depth Information
NP
Theorem 2.
C
LUSTERED
-L
EVEL
P
LANARITY
is
-complete.
Proof:
The problem clearly belongsto
NP
. We prove the
NP
-hardness. Given
an instance
) of
T
-
L
EVEL
P
LANARITY
as in the proof of Theorem 1; then, starting from (
V,E,ʳ,
A, C
of B
ETWEENNESS
, we construct an instance (
V,E,ʳ,
T
),
we construct an instance (
V,E,ʳ,T
) of CL-P
LANARITY
that is cl-planar if and only
if (
V,E,ʳ,
T
T
T
-level planar. This, together with the fact that (
V,E,ʳ,
T
T
) is
) is
-
A, C
level planar if and only if
is a positive instance of B
ETWEENNESS
, implies the
NP
-hardness of CL-P
LANARITY
. Refer to Fig. 2(b).
Cluster hierarchy
T
is constructed as follows. Initialize
T
with a root
μ
2
m
+1
.Next,
for
i
=
m,...,
1,let
u
ʴ
(
i
) bealeafof
T
that is child of
μ
2
i
+1
; add an internal node
ʽ
2
i
+1
to
T
as a child of
μ
2
i
+1
; then, let
u
ʱ
(
i
) and
u
ʲ
(
i
) be leaves of
T
that are children
of
ʽ
2
i
+1
; add an internal node
μ
2
i
to
T
as a child of
ʽ
2
i
+1
.Further, let
u
ʱ
(
i
) be a leaf
of
T
that is a child of
μ
2
i
; add an internal node
ʽ
2
i
to
T
as a child of
μ
2
i
; then, let
u
ʲ
(
i
)
and
u
ʴ
(
i
) be leaves of
T
that are children of
ʽ
2
i
; add an internal node
μ
2
i−
1
to
T
as a
child of
ʽ
2
i
. Finally, let vertices
v
∈
V
0
and
v
j
∈
V
1
,for
j
=1
,...,n
,beleavesof
T
that are children of
μ
1
.
We prove that (
V,E,ʳ,T
) is cl-planar if and only if (
V,E,ʳ,
T
) is
T
-level planar.
Suppose that (
V,E,ʳ,T
) admits a cl-planar drawing
ʓ
. Construct a
T
-level pla-
nar drawing
ʓ
∗
of (
V,E,ʳ,
) by removing from
ʓ
the clusters of
T
. The draw-
ing of (
V,E,ʳ
) in
ʓ
∗
is level-planar, since it is level-planar in
ʓ
.Further, for each
i
=1
,...,m
,vertex
u
ʱ
(
i
) does not appear between
u
ʲ
(
i
) and
u
ʴ
(
i
) along
L
2
i
,since
u
ʲ
(
i
)
,u
ʴ
(
i
)
T
ʽ
2
i
;analogously, vertex
u
ʴ
(
i
) does not appear between
u
ʱ
(
i
) and
u
ʲ
(
i
) along
L
2
i
+1
,since
u
ʱ
(
i
)
,u
ʲ
(
i
)
∈
ʽ
2
i
and
u
ʱ
(
i
)
/
∈
ʽ
2
i
+1
and
u
ʴ
(
i
)
/
ʽ
2
i
+1
. Hence, the
order of the vertices of
V
2
i
and
V
2
i
+1
along
L
2
i
and
L
2
i
+1
, respectively, are compatible
with trees
T
2
i
and
T
2
i
+1
. Finally, the order in which the vertices of
V
0
and
V
1
appear
along lines
L
0
and
L
1
are trivially compatible with
T
0
and
T
1
, respectively.
Suppose that (
V,E,ʳ,
∈
∈
-level planar drawing
ʓ
∗
; we describe how
to construct a cl-planar drawing
ʓ
of (
V,E,ʳ,T
).Assume that
ʓ
∗
is a straight-line
drawing, which is not a loss of generality [8]. Initialize
ʓ
=
ʓ
∗
. Draw each cluster
ʱ
in
T
as a convex region
R
(
ʱ
) in
ʓ
slightly surrounding the border of the convex hull of its
vertices and slightly surrounding the border of the regions representing the clusters that
are its descendants in
T
.Let
j
be the largest index such that
V
j
contains a vertex of
ʱ
.
Then,
R
(
ʱ
) contains all and only the vertices that are descendants of
ʱ
in
T
; moreover,
any two clusters
ʱ
and
ʲ
in
T
are one contained into the other, hence
R
(
ʱ
) and
R
(
ʲ
)
do not cross; finally, we prove that no edge
e
in
E
crosses more than once the boundary
of
R
(
ʱ
) in
ʓ
. First, if at least one end-vertex of
e
belongsto
ʱ
,then
e
and the boundary
of
R
(
ʱ
) cross at most once, given that
e
is a straight-line segment and that
R
(
ʱ
) is
convex. All the vertices in
V
0
∪
T
T
) admits a
V
j−
1
and at least two vertices of
V
j
belong to
ʱ
,
hence their incident edges do not cross the boundary of
R
(
ʱ
) more than once. Further,
all the vertices in
V
j
+1
∪
...
∪
V
2
m
+3
have
y
-coordinates larger than every point of
R
(
ʱ
), hence edges between them do not cross
R
(
ʱ
). It remains to consider the case in
which
e
connects a vertex
x
1
in
V
j
not in
ʱ
(there is at most one such vertex) with a
vertex
x
2
in
V
j
+1
∪
...
∪
V
2
m
+2
; in this case
e
and
R
(
ʱ
) do not cross given that
x
1
is
outside
R
(
ʱ
),that
x
2
has
y
-coordinate larger than every point of
R
(
ʱ
),andthat
R
(
ʱ
)
is arbitrarily close to the convex hull of its vertices.
...
∪
