Information Technology Reference
In-Depth Information
P
e
+1
,n−
1
t
(
S
)=
v
e
+1
P
a,b
t
(
S
) =
v
b
+1
P
b
+2
,j
t
(
S
) =
v
j
+1
E
C
P
i,a−
2
v
c
P
j
+1
,n−
1
B
D
P
a,b
v
b
+1
D
v
c−
1
v
b
+2
P
b
+1
,n−
1
v
b
+2
D
C
v
a
v
b
+1
B
A
C
v
a−
1
A
P
c,e
A
b
(
S
)=
v
a
B
P
a,b
P
1
,a−
1
P
1
,i−
1
P
b
+2
,c−
2
b
(
S
)=
v
i
b
(
S
)=
v
a
P
1
,a−
1
(a)
(b)
(c)
Fig. 3.
Constructions for (a) Case 4B, (b) Case 4C, and (c) Case 4D when
P
b
+2
,c−
2
is non-empty
(if
c
=
b
+2the set
C
is empty; if
a
=
c
and
b
=
e
the sets
B
and
D
are not distinguished).
mapped to
b
(
S
).Let
D
be the
n − b
highest points of
S
r
∪{t
(
S
)
}
. By Lemma 3, we
can embed
P
b
+1
,n−
1
on
D
such that vertex
v
b
+1
is mapped to
t
(
S
).Let
B
be the
a − i
leftmost points of (
S
\
A
)
∪{
b
(
S
)
}
.If
a
=
i
then
B
is empty. Otherwise, since
i>ʱ
,
(
B
)=
b
(
B
)=
b
(
S
) and since
a
ʲ
, the points
t
(
B
) and
r
(
B
) are consecutive in
B
.
Thus,
B
is a strip-convex point set and by Lemma 4 we can embed the
≤
-path
P
i,a−
2
on
B
such that vertex
v
i
is mapped to
b
(
S
) and vertex
v
a−
1
is mapped to either
t
(
B
) or
r
(
B
).Let
C
=
S
{
U,R
}
.Weembed
P
a,b
on
C
by sorting the
points by increasing
y
-coordinate. Thus, vertex
v
a
is mapped to
b
(
C
) and vertex
v
b
+1
is mapped to
t
(
S
).If
a
=
i
,vertex
v
i
=
v
a
is already mapped to
b
(
S
),thusatthisstep
we only embed the vertices of the
\
(
A
∪
B
∪D
)
∪{
t
(
S
)
}
-path
P
a
+1
,b
.
Next we merge the constructed PDCEs of
P
1
,i−
1
,P
i,a−
2
,P
a,b
,and
P
b
+1
,n−
1
.If
a
=
i
,
the edge
d
i
points upward since
v
i
is mapped to
b
(
S
). Otherwise, since
v
a−
1
is mapped
to
t
(
B
) or
r
(
B
),
v
a
is mapped to
b
(
C
),
B
and
C
are separable by a vertical line, and
edge (
v
a−
1
,v
a
) points to the right and does not cross the remaining drawing.
Recall that this case considers the situation where
i>ʱ
. In case
i
{
U
}
≤
ʱ
, we know that
d
ʱ
∈{
. If it happens that
d
ʱ
=
R
, the construction can be accomplished identi-
cally by considering index
ʱ
+1everywhere in place of
i
. Here, Lemma 2 guarantees
a mapping of
P
1
,ʱ
with
v
ʱ
+1
on
b
(
S
) since it is the rightmost point of
A
and
d
ʱ
=
R
.
Case 4C:
i ≤ ʱ
and
j<ʲ
. This case is symmetric to Case 4B. If
d
ʱ
=
R
the
embedding is constructed as explained at the end of Case 4A. Otherwise
d
ʱ
=
U
and
we again identify the maximal
U,R
}
-subpath
P
a,b
of
P
containing
d
ʱ
.Thestructure of
the path in this case is shown in Fig. 4 and the embedding in Fig.3(b).
Also, similar to Case 4B, we can use this construction to embed a path where
j
{
U
}
≥
ʲ
and
d
ʲ
=
R
. For that, consider the illustration of Fig.3(b).Weset
D
to contain only
points to the right of
t
(
S
) and
t
(
S
),i.e.,
.By
Lemma 3, we can map
v
ʲ
to
t
(
S
),since
d
ʲ
=
R
and
t
(
S
) is the leftmost point of
|D|
=
n
−
ʲ
+1.Weembed
P
ʲ,n−
1
on
D
D
.
The remaining construction is identical.
Case 4D:
i
≤
ʱ
and
j
≥
ʲ
,
d
ʱ
=
d
ʲ
=
U
.Let
P
a,b
,
a
≤
ʱ
≤
b
, be the maximal
{
U
}
-subpath of
P
containing
d
ʱ
. Similarly, let
P
c,e
,
c
≤
ʲ
≤
e
, be the maximal
{
U
}
-subpath of
P
containing
d
ʲ
. If there is no
R
-edge between
d
ʱ
and
d
ʲ
then
a
=
c
