Information Technology Reference
In-Depth Information
t
(
S
)
t
(
S
) =
v
m
v
b
=
t
(
S
)
P
1
,a−
1
A
P
1
,m
P
1
,m
B
P
a,b
C
P
m
+1
,n−
1
P
m
+1
,n−
1
P
b
+1
,n−
1
b
(
S
)=
v
m
+1
b
(
S
)
v
a
=
b
(
S
)
(a)
(b)
(c)
Fig. 1.
Illustration of the construction in Cases 1-3
Lemma 5. For the latter case, observe that in
M
(
S
), point
t
(
M
(
S
)) is to the right of
(
S
)). Moreover,
P
I
is an
(
P
I
) is again an
b
(
M
{
U,D,L
}
-path, and
M
{
U,D,R
}
-
(
P
I
) on
path. By Lemma 5, there exists a PDCE
E
of
M
M
(
S
). By Observation 3,
) is a PDCE of
P
I
on
S
.Due to Observation 1,
)
I
is a PDCE of
P
on
S
.
M
(
E
M
(
E
Case 2:
P
is an
{
U,D,L
}
-path. Observe that
P
I
{
U,D,R
}
E
is an
-path. Let
be a
PDCE of
P
I
on
S
, which exists by Case 1. Then
E
I
is a PDCE of
P
on
S
.
Case 3:
P
is an
{
U,L,R
}
-path. Thus,
R
(
P
) is an
{
U,D,L
}
-path. DuetoCase2,there
exists a PDCE
E
of
R
(
P
) on
R
(
S
). By Observation 2,
R
(
E
) is a PDCE of
P
on
S
.
Case 4:
P
is a
{
D,L,R
}
-path. Notice that
R
(
P
) is an
{
U,D,R
}
-path. Thus, for a
PDCE
E
of
R
(
P
) on
R
(
S
), which exists duetoCase1,
R
(
E
) is a PDCE of
P
on
S
.
This concludes the proof of the theorem.
Proof of Lemma 5.
Let
S
denote the subset of
S
containing all points on the left of the
line through
b
(
S
) and
t
(
S
),andlet
m
=
|
S
|
. We distinguish several cases based on the
labels
d
m
and
d
m
+1
.
Case 1:
d
m
=
D
,
d
m
+1
∈{
U,R
}
(see Fig. 1(a) for an illustration). We embed
P
1
,m
on
S
l
∪{
using Algorithm B
ACKWARD
E
MBEDDING
. By Lemma 2, vertex
v
m
+1
is mapped to
b
(
S
). Then, we embed
P
m
+1
,n−
1
on
S
r
∪{
b
(
S
)
}
t
(
S
)
,b
(
S
)
}
in the way given
by Lemma 3. Since
(
S
r
∪{
t
(
S
)
,b
(
S
)
}
)=
b
(
S
r
∪{
t
(
S
)
,b
(
S
)
}
)=
b
(
S
) and
d
m
+1
∈
{
,vertex
v
m
+1
is mapped to
b
(
S
).Thus, the union of these embeddingsisaPDCE
of
P
on
S
.
Case 2:
d
m
∈{U,R}
U,R
}
,
d
m
+1
=
D
(see Fig.1(b)).Weembed
P
1
,m
on
S
l
∪{t
(
S
)
}
using Algorithm B
ACKWARD
E
MBEDDING
. By Lemma 2, vertex
v
m
+1
is mapped to
t
(
S
) since
r
(
S
l
∪{t
(
S
)
}
)=
t
(
S
l
∪{t
(
S
)
}
)=
t
(
S
) and
d
m
∈{U,R}
.Due to Lemma 3,
we can embed
P
m
+1
,n−
1
on
S
r
∪{
t
(
S
)
,b
(
S
)
}
such that vertex
v
m
+1
is mapped to
t
(
S
),
since
t
(
S
r
∪{
t
(
S
)
,b
(
S
)
}
)=
t
(
S
) and
d
m
+1
=
D
.Thus, the union of these embeddings
is a PDCE of
P
on
S
.
Case 3:
d
m
=
D
,
d
m
+1
=
D
(see Fig.1(c)).Let
P
a,b
, 1
≤
a
≤
m<m
+1
≤
b
≤
n
1, be the maximal subpath of
P
containing
d
m
,
d
m
+1
and only
D
labels. Let
A
be the
a
highest points of
S
l
∪{
−
m
.Weembed
P
1
,a−
1
on
A
using Algorithm B
ACKWARD
E
MBEDDING
. By Lemma 2, vertex
v
a
is
mapped to
t
(
S
),since
d
a−
1
∈{
t
(
S
)
}
. Observe that
A
exists since
a
≤
U,R
}
and
r
(
A
)=
t
(
A
)=
t
(
S
).Let
C
be the
n
−
b
lowest points of
S
r
∪{
b
(
S
)
}
.Since
|
S
r
∪{
b
(
S
)
}|
=
n
−
m
−
1,and
b
≥
m
+1,thus
n
−
b
≤
n
−
m
−
1, and therefore
C
exists. By Lemma 3, we can embed
P
b
+1
,n−
1
on
