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) ʓ .
Search WWH ::




Custom Search