Information Technology Reference
In-Depth Information
{
U, D, R
}
-path
v
i−
1
{
U, R
}
-path
v
j
+1
{
U, D, R
}
-path
t
(
S
) =
v
j
+1
v
j
+2
d
j
+1
=
D
v
i
d
i−
1
=
D
P
1
,i−
1
C
P
i,j
A
B
{
U, D, R
}
-path
v
i−
1
{U, R}
-path
v
a−
1
{
U
}
-path
{U, D, R}
-path
v
b
+2
v
i
d
i−
1
=
D
v
a
v
b
+1
d
b
+1
=
R/D
P
j
+1
,n−
1
d
a−
1
=
R
b
(
S
)=
v
i
(a)
(b)
Fig. 2.
(a) Structure of the path in Cases 4A (above) and 4B (below) (b) Construction in Case 4A
C
such that
v
b
+1
is mapped to
b
(
S
) since
(
C
)=
b
(
C
)=
b
(
S
) and
d
b
+1
∈{
U,R
}
.
Let
B
be (
S
.Weembedthe
D
-path
P
a,b
on
B
, starting with
v
a
at
t
(
S
) and ending with
v
b
+1
at
b
(
S
), by sorting the points of
B
by decreasing
y
-
coordinate. Merging the PDCEs for
P
1
,a−
1
,P
a,b
,and
P
b
+1
,n−
1
, we obtain a PDCE of
P
on
S
.
Case 4:
d
m
,d
m
+1
∈{
\
(
A
∪
C
))
∪{
t
(
S
)
,b
(
S
)
}
1 be the
maximal subpath of
P
containing
d
m
,d
m
+1
and only
U/R
-labels. Thus
d
i−
1
=
d
j
+1
=
D
, if they exist. Let
ʱ
(resp.
ʲ
) denote the number of points of
S
lying to the left of
b
(
S
) (resp.
t
(
S
),including
t
(
S
)). We consider several cases based on how the indices
i
,
j
are related to the indices
ʱ
,
ʲ
.Theintuition behind this is to distinguish whether or
not the points that are vertically between
b
(
S
) and
t
(
S
) are enoughtoembed
P
i,j
.
Case 4A:
i>ʱ
and
j<ʲ
, i.e., the points vertically between
b
(
S
) and
t
(
S
) are enough
to embed
P
i,j
(see Fig.2).
Let
A
be the
i
lowest points of
S
l
∪{
U,R
}
.Let
P
i,j
where 1
≤
i
≤
m<m
+1
≤
j
≤
n
−
m
. By Lemma 2, we can
embed
P
1
,i−
1
on
A
such that
v
i
is mapped to
b
(
S
).Let
C
be the
n
b
(
S
)
}
;
A
exists since
i
≤
−
j
highest points of
S
r
∪{
m
. By Lemma 3, we can embed
P
j
+1
,n−
1
on
C
such that
v
j
+1
is mapped to
t
(
S
) since
d
j
+1
=
D
.Let
B
be (
S
t
(
S
)
}
;
C
exists since
n
−
j<n
−
\
(
A
∪
C
))
∪{
b
(
S
)
,t
(
S
)
}
.
Since
i>ʱ
,
(
B
)=
b
(
B
)=
b
(
S
), and since
j<ʲ
,
r
(
B
)=
t
(
B
)=
t
(
S
).Thus,
B
is
a strip-convex point set. By Lemma 4, we can embed the
-path
P
i,j
on
B
such
that
v
i
lies on
b
(
S
) and
v
j
+1
lies on
t
(
S
).Bymerging the constructed embeddingsof
P
1
,i−
1
,P
i,j
,and
P
j
+1
,n−
1
, we obtain a PDCE of
P
on
S
.
Observe that if either
i −
1=
ʱ
and
d
ʱ
=
R
or
j
+1=
ʲ
and
d
ʲ
=
R
or both, then
the embedding can be constructed identically. In case
d
ʱ
=
R
,vertex
v
i
is mapped to
r
(
A
)=
b
(
S
). In case
d
ʲ
=
R
,vertex
v
j
+1
is mapped to
(
C
)=
t
(
S
).Thus, these
embeddings can be merged with the above embedding of
P
i,j
on
B
.
Case 4B:
i>ʱ
and
j
{
U,R
}
.If
d
ʲ
=
R
then the embedding is
constructed as explained at the end of Case 4A. In the following we assume
d
ʲ
=
U
.
Let
P
a,b
,i
≥
ʲ
. In this case
d
ʲ
∈{
U,R
}
j
be the maximal subpath of
P
containing
d
ʲ
and only
U
-
edges; see Fig. 2(a)(below) for the structure of the constructed path. If
a>i
,
d
a−
1
=
R
.
Otherwise, if
a
=
i
then
d
a−
1
=
D
,i.e.,the
≤
a
≤
ʲ
≤
b
≤
{
U,R
}
-path
P
i,a−
2
is empty. Let
A
be
the
i
lowest points of
S
l
∪{
(see Fig. 3(a)). Notice that
A
is a left-sided point
set and
b
(
A
)=
b
(
S
). We can embed
P
1
,i−
1
on
A
by Lemma 2 such that vertex
v
i
is
b
(
S
)
}
