Information Technology Reference
In-Depth Information
Outer
Standard
P
Partial
rotation
Level
Partitioned
2-page
ec
-planar
Partial
Rotation
(with flips)
Radial
Level
Partially
Embedded
Proper
Clustered
Level
Proper
T
Partitioned
T
-coherent
2-page
-level
ec
-planar
with free
edges
?
[3]
Clustered (
c
)
SEFE
2
[1]
Clustered
level (
cl
)
T
-level
Partitioned
3-Page
Upward
SEFE
3
[1]
NPC
Partitioned
T
Weak
realizability
[4]
-coherent
3-page
SEFE
Fig. 1.
Updates on the classification proposed by Schaefer in [12]. Dashed lines represent the
boundaries between problems that were known to be polynomial-time solvable, problems that
were known to be
-complete, and problems whose complexity was unknown before this pa-
per. Solid lines represent the new boundaries according to the results of this paper. Reductions that
can be transitively inferred are omitted. Results proved after [12] are equipped with references.
The prefix “proper” has been added to two classes in [12] to better clarify their nature.
NP
Theorem 1.
T
-L
EVEL
P
LANARITY
is
NP
-complete.
Proof:
The problem clearly belongsto
NP
. We prove the
NP
-hardness. Given an
instance
of B
ETWEENNESS
, we construct an equivalent instance (
V,E,ʳ,T
)
of
T
-L
EVEL
P
LANARITY
as follows. Let
A
=
{
1
,...,n}
A, C
.Graph(
V,E
)
is a tree composed of
n
paths all incident to a common vertex
v
. Refer to Fig. 2(a).
Initialize
V
=
and
m
=
|C|
be a tree with a single node
v
.
For each
j
=1
,...,n
,addavertex
v
j
to
V
and an edge (
v,v
j
) to
E
, with
ʳ
(
v
j
)=1.
Also, let
T
1
∈T
{
v
}
,
E
=
∅
,and
ʳ
(
v
)=0.Let
T
0
∈T
be a star whose leaves are all the vertices of level
V
1
.Further, for each
j
=1
,...,n
, we initialize variable
last
(
j
)=
v
j
.
Then, for each
i
=1
,...,m
, consider the triple
t
i
=
. Add six vertices
u
ʱ
(
i
),
u
ʱ
(
i
),
u
ʲ
(
i
),
u
ʲ
(
i
),
u
ʴ
(
i
),and
u
ʴ
(
i
) to
V
with
ʳ
(
u
ʱ
(
i
)) =
ʳ
(
u
ʲ
(
i
)) =
ʳ
(
u
ʴ
(
i
))
=2
i
and
ʳ
(
u
ʱ
(
i
)) =
ʳ
(
u
ʲ
(
i
)) =
ʳ
(
u
ʴ
(
i
)) = 2
i
+1.Also,addedges (
last
(
ʱ
)
,u
ʱ
(
i
)),
(
last
(
ʲ
)
,u
ʲ
(
i
)), (
last
(
ʴ
)
,u
ʴ
(
i
)), (
u
ʱ
(
i
)
,u
ʱ
(
i
)), (
u
ʲ
(
i
)
,u
ʲ
(
i
)),and(
u
ʴ
(
i
)
,u
ʴ
(
i
)) to
E
.Further, set
last
(
ʱ
)=
u
ʱ
(
i
),
last
(
ʲ
)=
u
ʲ
(
i
),and
last
(
ʴ
)=
u
ʴ
(
i
).Let
T
2
i
∈T
beabinarytreewitharoot
r
2
i
, an internal node
x
2
i
and a leaf
u
ʱ
(
i
) both adjacent to
r
2
i
, and with leaves
u
ʲ
(
i
) and
u
ʴ
(
i
) both adjacent to
x
2
i
. Moreover, let
T
2
i
+1
∈T
ʱ, ʲ, ʴ
be
a binary tree with a root
r
2
i
+1
, an internal node
x
2
i
+1
and a leaf
u
ʴ
(
i
) both adjacent to
r
2
i
+1
, and with leaves
u
ʱ
(
i
) and
u
ʲ
(
i
) both adjacent to
x
2
i
+1
.
