Information Technology Reference
In-Depth Information
height is at most 3 n +3 H
6. Hence ʓ is a drawing on an integer grid of size
(3 n +4 W
×
(3 n +4 H
4).Since W + H
(4 n
2 Δ 0
10) / 3 (see Remark 1), the
4)
area can be at most (3 n +4(2 n
32 . 12 n 2 .
Bends per Edge: If ( v,v )isan l -edge or r -edge in ʓ G , which starts at v
and ends at v , then the edge has at most 2 bends: one before entering A v ,and
another at the boundary of A v .If( v,v )isan m -edge, then it contains one bend
on M , and another bend on the boundary of A v .The l -and r -edges that connect
a primary vertex to its parent, do not contain any bend. Since Δ 0 <n/ 2and
leaf ( T m ) <n , the drawing has at most 6 n
Δ 0
5) / 3) 2 = ((17 n
4 Δ 0
20) / 3) 2
11 n/ 2 bends.
Angular Resolution: To compute the angular resolution, observe that the
smallest possible angle ʸ at v is realized by a pair of consecutive integer grid
points on the boundary of A v where one of them is the corner of A v , e.g., see
Figure 6(a). Since A v is a grid of size (2
leaf ( T l )
leaf ( T r )
d ( v ) / 2
+1)
×
(2
d ( v ) / 2
+ 1), the
length of the line segment l connecting the center to any corner is 2
d ( v ) / 2
.
Hencewehave ʸ =arctan
1 / 2 > 1 /d ( v ), by the MacLaurin series
expansion of arctan [12]. Observe that any edge e that intersects some grid A v ,
where v does not correspond to any end vertex of e ,mustbean m -edge. We can
avoid any such intersection by choosing for each vertex u , a rectangular grid of
size (2
1 / 2
( 2
d ( v ) / 2
+ 1) (instead of A u ), where u (respectively,
u ) is the vertex with the largest degree over all the vertices on the horizontal
(respectively, vertical) line through u . For example, see the gray rectangles in
Figure 5(d). However, the angular resolution increases to 1 .
d ( u ) / 2
d ( u ) / 2
+1)
×
(2
Theorem 1. Every n-vertex maximal planar graph admits a 2 -bend polyline
drawing ʓ with angular resolution at least 1 /d ( v ) for each vertex v,andarea
at most (3 n +4 W
10) / 3 .
Within the same area, we can assign each vertex v in ʓ a bounding box of size
(2
×
(3 n +4 H
4) ,whereW + H
(4 n
2 Δ 0
4)
+1) that only intersect with the edges incident to
v, but the angular resolution increases to 1 /Δ.
d ( v ) / 2
×
d ( v ) / 2
+1)
(2
4 Trade-Offs between Angular Resolution and Area
In this section we show that one can significantly improve the area with an small
expense of angular resolution. We consider the following two scenarios.
Angular Resolution is γ/d ( v ), where γ
[0 . 8 , 1]: Observe that the
bottom-left quadrants of A v (with respect to the center C ( v )) has at most
2
d m ( v ) boundary points, which are sucient to route the m -
edges, and sometimes necessary. However, the boundary points that are available
to route the l -edges (similarly, r -edges) are significantly more than necessary, e.g.,
the number of boundary points to route the l -edges is 3
d ( v ) / 2
1
2 (lying on
the bottom-right quadrants and on the right-boundary of A v ). Hence assigning
agridofsize(
d ( v ) / 2
d ( v ) / 2
+1+
d ( v ) / 4
)
×
(
d ( v ) / 2
+1+
d ( v ) / 4
)toeachvertex
v would be sucient for routing the edges.
Observe that for each vertex v , the increase in width is at most (
d ( v ) / 2
+
d ( v ) / 4
)
(3 d ( v ) / 4 + 1). Since one column may contain multiple vertices, and
 
Search WWH ::




Custom Search