Information Technology Reference
In-Depth Information
{U, D, R}
-path
v
a−
1
{U}
-path
{U, R}
-path
{U, D, R}
-path
v
j
+2
v
a
d
a−
1
=
R/D
v
b
+1
v
b
+2
v
j
+1
d
j
+1
=
D
d
b
+1
=
R
{U, D, R}
-path
v
a−
1
{U}
-path
{U, R}
-path
{U}
-path
v
c
{U, D, R}
-path
v
e
+2
v
a
d
a−
1
=
R/D
v
b
+1
v
b
+2
v
c−
1
d
c−
1
=
R
v
e
+1
d
b
+1
=
R
d
e
+1
=
D/R
Fig. 4.
Structure of the path in Cases 4C (above) and 4D (below)
and
b
=
e
. If there is a single
R
-edge between them then
c
=
b
+2.Otherwise,
P
b
+2
,c−
2
is a
-path containing at least one vertex; see Fig. 4 for this case.
We embed the
{
U,R
}
{
U,D,R
}
-path
P
1
,a−
1
on the
a
lowest points, denoted by
A
,of
S
∪
{
. By Lemma 2, we can map
v
a
to
b
(
S
), since the rightmost point of
A
is
b
(
S
)
and
d
a−
1
∈{
b
(
S
)
}
D,R
}
. By Lemma 3, we can embed
P
e
+1
,n−
1
on the
n
−
e
−
1 highest
points, denoted by
E
,of
S
r
∪{
t
(
S
)
}
,such that
v
e
+1
is mapped to
t
(
S
), since it is the
leftmost point of
E
and
d
e
+1
∈{
.Fig. 3(c) shows the case where
P
b
+2
,c−
2
is
non-empty. However, it presents the idea of the embedding in the remaining cases as
well.
If
a
=
c
and
b
=
e
then
P
a,e
is a
D,R
}
,
by sorting the points by increasing
y
-coordinate. This completes the construction of a
PDCE of
P
on
S
.Otherwise,welet
B
(resp.
{
U
}
-path. We embed it on
S
\
(
A
∪
E
)
∪{
b
(
S
)
,t
(
S
)
}
D
)bethe
b
−
a
+2leftmost (resp.
e
−
c
+2
rightmost) points of
S
\
(
A
∪
E
)
∪{
b
(
S
)
,t
(
S
)
}
.Weembed
P
a,b
(resp.
P
c,e
)on
B
(resp.
D
) by sorting its points by
y
-coordinates.
If
c
=
b
+2,the
-paths
P
a,b
and
P
c,e
are joined by a single
R
-edge. Since
v
b
+1
is to the left of
v
b
+2
=
v
c
, the constructed embedding yields a direction-consistent
embedding of the edge (
v
b
+1
,v
b
+2
) and this completes the construction of a PDCE of
P
on
S
.Otherwise,
P
b
+2
,c−
2
is an
{
U
}
-path that contains at least one vertex and
d
b−
1
=
d
c−
1
=
R
.Weembed
P
b
+2
,c−
2
on the remaining free points, i.e., on the point
set
C
=
S
{
U,R
}
,theset
C
is separated
from the remaining points by vertical lines. Thus,
(
C
) and
b
(
C
) are either consecutive
or coincide. Similarly, points
t
(
C
) and
r
(
C
) are either consecutive or coincide. Thus,
C
is a strip-convex point set. By Lemma 4, we can embed
P
b
+2
,c−
2
on
C
such that
v
b
+2
is mapped to one of
(
C
) or
b
(
C
),and
v
c−
1
to one of
t
(
C
) or
r
(
C
).As
v
b
+2
is
mapped to the highest point of
B
and
v
c
is mapped to the lowest point of
D
,weinfer
that the obtained embedding of
P
on
S
is planar. Since
d
b
+1
=
d
c−
1
=
R
and by the
fact that
C
is separated from
B
and
\
(
A
∪
B
∪D∩
E
). By construction of
B
and
D
D
by vertical lines, it is also direction-consistent.
This concludes the proof of the lemma.
5
Four-Directional Paths
The proof of the following theorem, which can be found in the full version [1], is based
on a counterexample showing that the path
P
=
LULRDR
does not admit a PDCE on
a left-sided point set.
