Information Technology Reference
In-Depth Information
l
v
k
v
k
l
v
k
d
(
v
)
w
l
+1
ʸ
v
k
=(0
,
0)
d
(
v
)
/
2
h
d
(
v
)
/
4
ʱd
(
v
)
(
−d
(
v
)
,−h
)
C
(
v
)
(
v
)
d
(
v
)
/
2
C
(
v
)
d
(
v
)
/
2
C
d
(
v
)
/
2
ʸ
ʸ
w
r−
1
(a)
(d)
(e)
(b)
(c)
Fig. 6.
Illustration for angular resolution
the degree of each vertex is at least three, we are overcounting the increase for
(
n−W −
2) vertices. The amount of over computation for each such vertex
v
is
at least
3
d
(
v
)
/
4
+1
≥
3. Consequently, the total increase in the width in the
Expansion phase is now bounded by (
W
+2
i
=1
(3
d
(
v
i
)
/
4+1))
−
3(
n
−
W
−
2)
≤
3
n/
2+4
W
−
1. Similarly, the increase in height is at most 3
n/
2+4
H
+1.Since
W
+
H
≤
(4
n
−
2
Δ
0
−
10)
/
3, the area can be at most (3
n/
2+5(2
n
−
Δ
0
−
5)
/
3+
5)
2
23
.
37
n
2
. The number of bends remains the same, but the minimum angle
ʸ
is now at least 0
.
8
/d
(
v
), which is now determined by two consecutive points
along the bottom-right corner, as shown in Figure 6(b).
We can parametrize the grid size with a parameter
ʱ
, i.e., consider the grid
assigned to
v
as (
≤
d
(
v
)
/
2
+1+
ʱd
(
v
))
×
(
d
(
v
)
/
2
+1+
ʱd
(
v
)), where
ʱ
≥
1
/
4.
Then the increase in width is at most (
W
+2
i
=1
((
ʱ
+1
/
2)
d
(
v
i
)+1))
−
3(
n
−
W
−
(6
ʱn
+4
W
+ 8). Similarly, the increase
in height is at most (6
ʱn
+4
H
+ 8), respectively. Hence the area is at most
(6
ʱn
+4(
W
+
H
)
/
2 + 10)
2
≤
(6(
ʱ
+1
/
2)
n
−
3
n
+4
W
+8)
≤
2)
≤
(6
ʱn
+8
n/
3 + 10)
2
≈
(6
ʱ
+8
/
3)
2
n
2
. The angular
ʱ/
√
ʱ
2
+1
/
4
d
(
v
)
√
ʱ
2
+1
/
4
>
ʱ
resolution is at least
d
(
v
)(
ʱ
2
+1
/
4)
, as illustrated in Figure 6(c).
Theorem 2.
Every n-vertex maximal planar graph admits a
2
-bend polyline
drawing with angular resolution
ʱ
d
(
v
)(
ʱ
2
+1
/
4)
for each vertex v,andarea
(6
ʱn
+
4
W
+10)
×
(6
ʱn
+4
H
+10)
.Hereʱ
∈
[1
/
4
,
1
/
2]
,andW
+
H
≤
(4
n
−
2
Δ
0
−
10)
/
3
.
[0
.
3
,
0
.
5]:
Recall that the
new grid lines in the Expansion phase are inserted such that each vertex
v
has
h
=
ʲ
v
d
(
v
) free grid lines, where
ʲ
v
≥
Angular Resolution is
γ/d
(
v
), where
γ ∈
1
/d
(
v
), in each of the four sides (above,
below, left, right) around
v
, i.e.,
C
(
v
) is at the center of a free integer grid
A
v
of
size
h
h
. As in the Expansion phase, let
S
v
be the ordered set of horizontal free
grid lines along with the horizontal line through
v
, and let
S
v
be the ordered set
of vertical free grid lines along with the vertical line through
v
. We now show
that these free grids are sucient for routing the
l
-,
r
-and
m
-edges.
×
and
l
v
k
Routing
m
-edges:
Let
l
v
k
be the grid lines that are immedi-
and
S
v
k
, respectively. For each
w
ately below and to the left of
S
v
k
∈
{
, we now extend a line segment with slope +1 from
C
(
w
)
until we hit either
l
v
k
or
l
v
k
.Let
B
=
w
l
+1
,...,w
r−
1
}
be the set
of points on
l
v
k
and
l
v
k
reached by these extensions. We now extend these
extensions further to reach
C
(
v
k
), as follows:
{
b
(
w
l
+1
)
,...,b
(
w
r−
1
)
}