A framework for drawing planar graphs with curves and polylines

We describe a unified framework of aesthetic criteria and complexity measur es for drawing planar graphs with polylines and curves. This framework incl udes several visual properties of such drawings, including aspect ratio, ve rtex resolution, edge length, edge separation, and edge curvature, as well as complexity measures such as vertex and edge representational complexity and the area of the drawing. In addition to this general framework, we pres ent algorithms that operate within this framework. Specifically, we describ e an algorithm for drawing any n-vertex planar graph in an O(n) x O(n) grid using polylines that have at most two bends per edge and asymptotically-op timal worst-case angular resolution. More significantly, we show how to ada pt this algorithm to draw any n-vertex planar graph using cubic Bezier curv es, with all vertices and control points placed within an O(n)x O(n) intege r grid so that the curved edges achieve a curvilinear analogue of good angu lar resolution. All of our algorithms run in O(n) time. (C) 2000 Academic P ress.