Information Technology Reference
In-Depth Information
v
8
v
8
v
8
v
8
v
8
v
6
v
6
v
6
v
6
b
b
v
1
v
1
v
2
z
v
2
v
2
v
1
v
7
v
1
z
v
6
v
7
v
4
v
7
v
3
v
3
v
3
a
v
5
v
5
v
5
a
v
5
v
5
v
3
v
4
v
4
v
2
v
1
v
4
v
4
(a)
(b)
(c)
(d)
(e)
i
z
i
b
i
o
(j)
(f)
(g)
(h)
(i)
Fig. 2.
(a) A plane triangulation
G
,where
C
isshowninbold.(b)
ʓ
,where
v
4
=
a,v
8
=
b
and
v
2
=
c
.(c)
G
i
.(d)
H
, where the division vertices are shown in white. (e)
G
o
, where the edges added to
H
are shown in gray. (f)-(j) Drawing
G
.
Let
i
be a vertical line to the left of
z
in
ʓ
i
such that all the other vertices
of
ʓ
i
are in the left half-plane of
i
.Furthermore,
i
must be close enough such
that all the intersection points with the edges incident to
z
lie in between two
consecutive parallel lines. For each intersection point, we insert a division vertex
at that point and create a horizontal line through that vertex. Let
v
1
,v
2
,...,v
ʻ
be the division vertices on
i
in the order of decreasing
y
-coordinate, where for
each
i
,
v
i
is incident to the vertex
w
i
on
C
. Delete vertex
z
, but
not the division vertices. For each vertex
w
i
,if
d
o
(
w
i
)
>
3, then we place a set
of division vertices
v
i
,v
i
,...,v
d
o
(
w
i
)
−
i
below
v
i
and above the horizontal line
closest to
v
i
. Besides, these new division vertices must be suciently close to
v
i
such that drawing of the edges (
w
i
,v
i
), where 1
∈{
1
,
2
,...,ʻ
}
3, do not create
any edge crossing. Figures 2(f)-(h) illustrate this scenario. Finally, by Lemma 3,
we can modify
ʓ
i
such that the horizontal lines are equally spaced. Note that
ʓ
i
is a drawing on at most
x
+
ʻΔ
horizontal lines.
Since the division vertices in
ʓ
i
and
ʓ
o
take a set of consecutive horizontal
lines from their respective topmost lines, it is straightforward to merge these
two drawings on a set of
ʻΔ
+max
≤
j
≤
d
o
(
w
i
)
−
=4
n/
9+
O
(
ʻΔ
) horizontal lines.
We delete the edges on
C
, and consider all vertices of
C
as division vertices.
Since the division vertices correspond to the bends, each edge may contain at
most six bends (two bends to enter
ʓ
o
from
ʓ
i
, two bends on
C
, and two bends
to return to
ʓ
i
from
ʓ
o
). Since there are at most
ʻΔ
edges that may have
bends, the number of bends is at most 6
ʻΔ
in total. However, via 'flat-visibility
representation' (similar to the proof of Lemma 3) one can reduce the number of
bends to enter and exit
ʓ
o
by one, we omit the details due to space constraints.
Hence the number of bends reduces to 4
ʻΔ
. The following theorem summarizes
the result of this section.
{
x, y
}
