It is a well-known fact that every planar graph admits a planar straight-line drawing. The angular resolution of such a drawing is the minimum angle subtended by any pair of incident edges. The angular resolution of the graph is the supremum angular resolution over all planar straight-line drawings of the graph. In a recent paper by Formann et al. [Proc. 31st IEEE Sympos. on Found. of Comput. Sci., 1990, pp. 86–951, the following question is posed: Does there exist a constant $r( d ) > 0$ such that every planar graph of maximum degree d has angular resolution $ \geq r( d )$ radians? The present authors show that the answer is yes and that it follows easily from results in the literature on disk-packings. The conclusion is that every planar graph of maximum degree d has angular resolution at least $\alpha^d $ radians, $0 < \alpha < 1$ constant. In an effort to assess whether this lower bound is existentially tight (up to constant $\alpha $), a very natural linear program (LP) that bounds the angular resolution of a planar graph the authors analyze from above. The optimal value of this LP is shown to be $\Omega (1/d)$, which suggests that the $\alpha^d$ lower bound might be improved to $\Omega ( 1/d )$. Although this matter remains unsettled for general planar graphs, $\Omega ( 1/d )$ is shown to be a lower bound on angular resolution for outerplanar graphs. Finally, an infinite family of triangulated planar graphs with maximum degree 6 is constructed such that exponential area is required to draw each member in planar straight-line fashion with angular resolution bounded away from zero.

A famous theorem of I. Fa`ry states that any planar graph can be drawn in the plane so that all edges are straight-line segments and no two edges cross. The angular resolution of such a drawing is the minimum angle subtended by any pair of incident edges. The angular resolution of a planar graph is the maximum angular resolution over all such planar straight-line drawings of the graph. In a recent paper by Formann et al., Drawing graphs in the plane with high resolution, Symp. on Found. of Comp. Sci. (1990), the following question is posed: does there exist a constant r(d) > 0 such that every planar graph of maximum degree d has angular resolution ≥ r(d)? We answer this question in the affirmative by showing that any planar graph of maximum degree d has angular resolution at least αd radians where 0 < α < 1 is a constant. In an effort to assess whether or not this lower bound is existentially tight (up to constant α), we analyze a very natural linear program that bounds the angular resolution of any fixed planar graph G from Ω(1/d), although currently, we are unable to settle this issue for general planar graphs. For the class of outerplanar graphs with triangulated interior and maximum degree d, although currently, we are unable to settle this issue for general planar graphs. For the class of outerplanar graphs with triangulated interior and maximum degree d, we show not only that Ω(1/d) is lower bound on angular resolution, but in fact, this angular resolution can be achieved in a planar straight-line drawing where all interior faces are similar isosceles triangles. Additional results are contained in the full paper.

A book embedding of a graph consists of a linear ordering of the vertices along the spine of a book and an assignment of edges to pages so that edges on the same page do not intersect. The minimum number of pages in which a graph can be embedded is its pagenumber. The following results are presented: (1) any graph of genus g has pagenumber O( square root g); and (2) most n-vertex d-regular graphs have pagenumber Omega ( square root dn/sup 1/2-1/d/).>