Information Technology Reference
In-Depth Information
determined by the last line of
S
w
and first line of
S
w
,where
w
∈{
w
l
+1
,...w
r−
1
}
.
Figure 5(d) illustrates
M
with a dotted line. For each
w
∈{
w
l
+1
,...w
z
}
,we
now route the
m
-edge incident to
w
through the top-right corner
c
w
upto
M
,
and then to a distinct grid point on the leftmost boundary of
A
v
k
below
L
(
v
k
).
Observe that
d
m
(
v
k
)
/
2
≤
d
m
(
v
k
)
/
2+1
≤
(
d
(
v
k
)
−
3)
/
2+1
≤
(
d
(
v
k
)
−
1)
/
2.
Since (
d
(
v
k
)
(irrespective of the parity of
d
(
v
k
)), the
grid points on the leftmost boundary of
A
v
k
below
L
(
v
k
) are sucient to route all
the
m
-edges incident to
−
1)
/
2isatmost
d
(
v
k
)
/
2
,
we now route the
m
-edge incident to
w
through the top-right corner
c
w
upto
M
, and then to a distinct grid point to the left of
D
(
v
k
) on the bottommost
boundary of
A
v
k
.Since
{
w
l
+1
,...w
z
}
. Similarly, for each
w
∈{
w
z
+1
,...w
r−
1
}
1 (irrespective of the parity
of
d
(
v
k
)), we have sucient number of boundary points to route all the
m
-edges
incident to
d
m
(
v
k
)
/
2
≤
d
(
v
k
)
/
2
−
.
The
l
-and
r
-edges of
ʓ
n
contain edge overlapping on the left and down hands.
From the Expansion phase it is straightforward to observe that the
l
-edges that
are incoming to some vertex
v
in
ʓ
n
,areincidentto
D
(
v
), and properly intersects
the first half of the
S
v
.Let
be the nearest vertical grid line to the right of
S
v
,and
remove the parts of these
l
-edges that lie in between
D
(
v
)and
(except for the
l
-
edge incident to
C
(
v
)). Since all these
l
-edges lie below
S
v
, the points where these
l
-edges are incident to
can see all the grid points on the rightmost boundary of
A
v
and on the right-half of the bottommost boundary of
A
v
.Consequently,we
can route the
l
-edges to
C
(
v
) through these boundary grid points, which removes
the edge overlaps on
D
(
v
). Figure 5(e) illustrates such a scenario. Symmetrically,
we can remove the degeneracy of
r
-edges on
L
(
v
). Remark 2 and the property
that the lines in
S
v
and
S
v
do not contain any vertex except
v
ensure that
the above modifications do not introduce any edge crossing. Let the resulting
drawing be
ʓ
, which is a planar polyline drawing of
G
, e.g., see Figure 5(e).
Area:
By Lemma 2, the area before the Expansion phase was (
W
+2)
×
(
H
+2).
For each
i
,where1
≤ i ≤ W
+ 2, the Expansion phase increases the width of
the drawing by 2
d
(
u
i
)
/
2
,where
u
i
is the vertex with the largest degree on
the
i
th column. Hence the total increase is at most (
W
+2
{
w
z
+1
,...w
r−
1
}
i
=1
d
(
u
i
))
−
3(
n
−
W
−
≤
(6
n
−
−
3(
n
−
W
−
2) = 3
n
+3
W
−
2)
12)
6. Similarly, the increase in
v
1
v
1
v
1
v
1
v
8
v
8
v
v
v
k
8
8
v
6
3
v
4
v
7
w
l
+1
v
6
v
6
v
6
v
v
v
7
7
7
M
v
v
5
}
S
v
4
v
2
v
4
v
4
v
4
d
(
v
1
)=5
,d
(
v
2
)=4
,
d
(
v
3
)=5
,d
(
v
4
)=4
,
d
(
v
5
)=4
,d
(
v
6
)=4
,
d
(
v
7
)=5
,d
(
v
8
)=5
.
v
3
v
5
v
3
v
5
v
3
v
5
v
v
v
2
2
2
w
r−
c
w
r−
1
(a)
(b)
(c)
(d)
(e)
Fig. 5.
Illustration for (a)
ʓ
n
,(b)
S
v
k
,and(c)
ʓ
n
, where the grid
A
v
, for each vertex
v
, is shown in black squares. (d) Illustration for
M
.Notethat
A
w
s are bounded by
gray rectangles determined by
S
w
and
S
w
.(e)
ʓ
.