Seth Malitz
ABSTRACT
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.
- 1.R. Arrathoon ed., Optical Computing: Digital and Symbolic, Marcel Dekker Inc., 1989. Google Scholar
Digital Library
- 2.B. Becker, G. Hot#, On the optimal layout of planar graphs with fized boundary, SIAM J. Computing, vol. 16, no. 5, (1987) pp. 946-972. Google ScholarDigital Library
- 3.B. Becker, H.G. Osthof, Layout with wires of balanced length, Information and Computation, vol. 73 (1987)pp. 45-58. Google ScholarDigital Library
- 4.S. Bhatt, F. Leighton, A framework for solving VLSI layout problems, J. Comp. Syst. Sci., Vol. 28, (1984) pp. 300-343.Google ScholarCross Ref
- 5.N. Chiba, K. Onoguchi, T. Nisheziki, Drawing plane graphs nicely, Acta Informatica, 22 (1985), pp. 187-201.Google ScholarCross Ref
- 6.H.S.M. Coxeter, Introduction to Geometry, 2nd Ed., John Wiley and Sons, Inc., 1989.Google Scholar
- 7.P. Eades, R. Tamassia, Algorithms for drawing graphs: an annotated bibliography, TR CS-89-90, Dept. of Comp. Sci., Brown Univesity, 1989. Google ScholarDigital Library
- 8.I. Fhry, On straight-line representations of planar graphs, Acta Sci. Math. Szeged, vol. 1!1 (1948), pp. 229-233.Google Scholar
- 9.M. Formann, T. Hagerup, J. Haralambides, M. Kaufmann, F.T. Leighton, A. Simvonis, E. Welzl, G. Woeginger, Drawing graphs in t)ie plane with high resolution, 31st Symp. Found. of Comp. Sci. (1990), pp. 86-95.Google ScholarDigital Library
- 10.T. Kamada, S. Kawai, An algorithm for drawing general undirected graphs, Information Processing Letters 31 (1989) pp. 7-15. Google ScholarDigital Library
- 11.F. Lin, Optical holographic interconnection networks for parallel and distributed processing, Optical Computing Technical Digest Series, Vol. 9 (1989), pp. 150-153.Google Scholar
- 12.S. Malit#, A. Papakostas, On t.h.e angular resolution of planar graphs, submitted.Google Scholar
- 13.G. Miller, S-H. Teng, S. Vavasis, A unified geometric approach to graph separators, 32nd Symp. on Found. of Comp. Sci. (1991), pp. 538-547. Google ScholarDigital Library
- 14.J. Mogul, Efficient use of workstations for passive monitoring of local area networks, ACM 1990.Google ScholarDigital Library
- 15.W. P. Thurston, The geometry and topology of 3-manifolds, Princeton University Notes, 1988.Google Scholar
- 16.W.T. Tutte, How to draw a graph, Proc. London Math. Soc., (3) 13 (1963), pp. 743-768.Google ScholarCross Ref
Index Terms
- On the angular resolution of planar graphs
Recommendations
On the Angular Resolution of Planar Graphs
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 ...
Equitable colorings of planar graphs without short cycles
An equitable coloring of a graph is a proper vertex coloring such that the sizes of every two color classes differ by at most 1. Chen, Lih, and Wu conjectured that every connected graph G with maximum degree @D>=2 has an equitable coloring with @D ...
Adapted list coloring of planar graphs
Given an edge coloring F of a graph G, a vertex coloring of G is adapted to F if no color appears at the same time on an edge and on its two endpoints. If for some integer k, a graph G is such that given any list assignment L to the vertices of G, with |...
Comments