Information Technology Reference
In-Depth Information
I
1
-
I
4
hold for
G
2
,G
3
,...,G
k−
1
,where
k
−
1
<n
, and consider
that invariants
the insertion of vertex
v
k
.
Insertion of
v
k
:
Let
w
l
,w
l
+1
,...,w
r−
1
,w
r
be the neighbors of
v
k
on
P
k−
1
.
Consider an infinite horizontal line
h
that lies in between the horizontal grid
line determined by
L
(
w
l
) and the horizontal grid line immediately below
L
(
w
l
).
Similarly, let
v
be an infinite vertical line that lies in between the vertical grid
line determined by
D
(
w
r
) and the vertical grid line immediately to the left of
D
(
w
r
). We now add
v
k
considering the following cases. The case when
k
=
n
is
special, which is handled by Case 4.
Case 1 (
v
k
is a nonprimary vertex in both
T
l
and
T
r
):
We first perform
a 1-shift with respect to
h
. This increases the number of horizontal lines by 1
and ensures that
D
(
w
l
)containsatleast1gridpoint
p
that does not contain
any vertex or contact point. Similarly, we perform a 1-shift with respect to
v
, which increases the number of vertical lines by 1 and ensures that
L
(
w
r
)
contains at least 1 grid point
q
that does not contain any vertex or contact
point. We now consider the horizontal ray
r
p
that starts at
p
. Since the upper
envelope of
ʓ
k−
1
is
x
monotone and
p
does not contain any vertex or contact
point,
r
p
does not intersect
ʓ
k−
1
except at
p
. Similarly, we define a vertical ray
r
q
that starts at
q
, which does not intersect
ʓ
k−
1
except at
q
.Wenowplace
v
k
at the intersection point of
r
p
and
r
q
, and draw the edges (
v
k
,w
l
)and(
v
k
,w
r
).
Since
r
p
and
r
q
do not intersect
ʓ
k−
1
except at
p
and
q
, respectively, drawing
of these edges does not introduce any crossing. Figure 4(c) illustrates such a
scenario. We omit the proof that
ʓ
k
respects the invariants
I
1
-
I
4
due to space
constraints.
Case 2 (
v
k
is a primary vertex in
T
l
but a nonprimary vertex in
T
r
):
In this case we perform a 1-shift with respect to
v
, which increases the number
of vertical lines by 1 and ensures that
L
(
w
r
)containsatleast1gridpoint
q
that does not contain any vertex or contact point. Assume that
p
=
C
(
w
l
). We
now consider the horizontal ray
r
p
that starts at
p
. Since the upper envelope
of
ʓ
k−
1
is
x
monotone and
p
does not contain any vertex or contact point,
r
p
does not intersect
ʓ
k−
1
except at
p
. Similarly, we define a vertical ray
r
q
starting at
q
, which does not intersect
ʓ
k−
1
except at
q
.Wenowplace
v
k
at
the intersection point of
r
p
and
r
q
, and draw the edges (
v
k
,w
l
)and(
v
k
,w
r
).
Figure 4(e) illustrates such a scenario.
v
8
v
1
v
1
v
1
v
8
v
7
v
1
v
1
v
6
v
6
v
6
v
6
v
7
v
7
v
1
v
4
v
4
v
4
v
4
v
1
v
4
v
4
v
5
v
3
v
5
v
5
v
3
v
5
v
3
v
3
v
3
v
3
v
3
v
5
v
2
v
2
v
2
v
2
v
2
v
2
v
2
v
1
v
2
(a)
(b)
(c)
(d)
(f)
(g)
(h)
(e)
Fig. 4.
(a) A plane graph
G
and a minimum Schnyder realizer of
G
. (b)-(h) Illustration
for the drawing of
G \ T
m
.
