Information Technology Reference
In-Depth Information
r
2
i
+1
μ
2
i
+1
x
2
i
+1
ʽ
2
i
+1
T
2
i
+
1
L
2
i
+1
L
2
i
+1
u
ʱ
(
i
)
r
2
i
u
ʲ
(
i
)
x
2
i
u
ʴ
(
i
)
μ
2
i
ʽ
2
i
T
2
i
L
2
i
L
2
i
u
ʱ
(
i
)
u
ʲ
(
i
)
u
ʴ
(
i
)
T
1
L
1
L
1
v
ʱ
v
ʲ
v
ʴ
v
ʱ
v
ʲ
v
ʴ
L
0
L
0
v
v
(a)
(b)
Fig. 2.
Illustrations for the proof of (a) Theorem 1 and (b) Theorem 2
The reduction is easily performed in
O
(
n
+
m
) time. We prove that (
V,E,ʳ,
T
) is
T
-level planar if and only if
A, C
is a positive instance of B
ETWEENNESS
.
Suppose that (
V,E,ʳ,
T
) admits a
T
-level planar drawing
ʓ
. Consider the left-to-
right order
O
1
in which the vertices of level
V
1
appear along
L
1
. Construct an order
O
of the elements of
A
such that
ʱ
∈
A
appears before
ʲ
∈
A
if and only if
v
ʱ
∈
V
1
appears before
v
ʲ
∈
V
1
in
O
1
. In order to prove that
O
is a positive solution for
A, C
,
it suffices to prove that, for each triple
t
i
=
ʱ, ʲ, ʴ
∈
C
, vertices
v
ʱ
,
v
ʲ
,and
v
ʴ
appear either in this order or in the reverse order in
O
1
. Note that tree
T
2
i
enforces
u
ʱ
(
i
) not to lie between
u
ʲ
(
i
) and
u
ʴ
(
i
) along
L
2
i
; also, tree
T
2
i
+1
enforces
u
ʴ
(
i
) not
to lie between
u
ʱ
(
i
) and
u
ʲ
(
i
) along
L
2
i
+1
. Since the three paths connecting
u
ʱ
(
i
),
u
ʲ
(
i
),and
u
ʴ
(
i
) with
v
are
y
-monotone, do not cross each other, and contain
u
ʱ
(
i
) and
v
ʱ
,
u
ʲ
(
i
) and
v
ʲ
,and
u
ʴ
(
i
) and
v
ʴ
, respectively, we have that
v
ʱ
,
v
ʲ
,and
v
ʴ
appear
either in this order or in the reverse order in
O
1
.
Suppose that an ordering
O
of the elements of
A
exists that is a positive solution of
B
ETWEENNESS
for instance
. In order to construct
ʓ
, place the vertices of
V
1
along
L
1
in such a way that vertex
v
j
∈
A, C
V
1
is assigned
x
-coordinate equal to
s
if
j
is
the
s
-th element of
O
,for
j
=1
,...,n
.Also,for
i
=1
,...,m
,let
t
i
=
ʱ, ʲ, ʴ
∈
C
.
Place vertices
u
ʻ
(
i
) and
u
ʻ
(
i
), with
ʻ
,on
L
2
i
and
L
2
i
+1
, respectively, in
such a way that
u
ʻ
(
i
) and
u
ʻ
(
i
) are assigned
x
-coordinate equal to
s
if
ʻ
is the
s
-th
element of
∈{
ʱ, ʲ, ʴ
}
. Finally, place
v
at any point on
L
0
and draw the edges of
E
as straight-
line segments. We prove that
ʓ
is a
O
).First,
ʓ
is a level planar drawing of (
V,E,ʳ
), by construction. Further, for each
i
=1
,...,m
,
vertices
u
ʱ
(
i
),
u
ʲ
(
i
),and
u
ʴ
(
i
) appear along
L
2
i
either in this order or in the reverse
order; in both cases, the order is compatible with tree
T
2
i
.Analogously, vertices
u
ʱ
(
i
),
u
ʲ
(
i
),and
u
ʴ
(
i
) appear along
L
2
i
+1
either in this order or in the reverse order; in both
cases, the order is compatible with tree
T
2
i
+1
. Finally, the order in which vertices of
V
0
and
V
1
appear along
L
0
and
L
1
are trivially compatible with
T
0
and
T
1
, respectively.
T
-level planar drawing of (
V,E,ʳ,
T
