A Framework for Drawing Planar Graphs with Curves and Polylines

Goodrich, Michael T. and Wagner, Cristopher G. (1998) A Framework for Drawing Planar Graphs with Curves and Polylines. In: Graph Drawing 6th International Symposium, GD’ 98, August 13-15, 1998, Montréal, Canada , pp. 153-166 (Official URL: http://dx.doi.org/10.1007/3-540-37623-2_12).

Full text not available from this repository.

Abstract

We describe a unified framework of aesthetic criteria and complexity measures for drawing planar graphs with polylines and curves. This framework includes several visual properties of such drawings, including aspect ratio, vertex 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 present algorithms that operate within this framework. Specifically, we describe an algorithm for drawing any n-vertex planar graph in an O(n) \times O(n) grid using polylines that have at most two bends per edge and asymptotically-optimal worst-case angular resolution.More significantly, we show how to adapt this algorithm to draw any n-vertex planar graph using cubic Bézier curves, with all vertices and control points placed within an O(n) \times O(n) integer grid so that the curved edges achieve a curvilinear analogue of good angular resolution. All of our algorithms run in O(n) time.

Item Type:Conference Paper
Additional Information:10.1007/3-540-37623-2_12
Classifications:M Methods > M.600 Planar
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.540 Planar
M Methods > M.999 Others
P Styles > P.300 Curved
G Algorithms and Complexity > G.070 Area / Edge Length
G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.210 Bends
D Aesthetics > D.001 General
ID Code:263

Repository Staff Only: item control page

References

T. Chan, M.T. Goodrich, S.R. Kosaraju, and R. Tamassia. Optimizing area and aspect ratio in straight-line orthogonal tree drawings. In Proc. of the Symp. on Graph Drawing, GD'96, pages 63-75. Springer Verlag, September 1996.

M. Chrobak and T. Payne. A linear-time algorithm for drawing planar graphs. Inform. Process. Lett., 54:241-246, 1995.

H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10:41-51, 1990.

G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Algorithms for drawing graphs: An annotated bibliography. Comput. Geom. Theory Appl., 4: 235-282, 1994.

M. Formann, T. Hagerup, J. Haralambides, M. Kaufmann, F.T. Leighton, A. Symvonis, E. Welzl, and G. Woeginger. Drawing graphs in the plane with high resolution. SIAM J. Comput., 22:1035-1052, 1993.

E.R. Gansner, E. Koutsofios, S.C. North, and K. P. Vo. A technique for drawing directed graphs. IEEE Trans. Softw. Eng., 19:214-230, 1993.

A. Garg and R. Tamassia. Planar drawings and angular resolution: Algorithms and bounds. In J. van Leeuwen, editor, Algorithms (Proc. ESA '94), volume 855 of LNCS, pages 12-23. Springer-Verlag, 1994.

J. Hopcroft and R.E. Tarjan. Efficient planarity testing. J. ACM, 21(4):549-568, 1974.

Goos Kant. Algorithms for drawing planar graphs. PhD thesis, Dept. Comput. Sci., Univ. Utrecht, Netherlands, 1993.

Goos Kant. Drawing planar graphs using the canonical ordering. Algorithmica, 16:4-32, 1996. (Special issue on Graph Drawing, edited by G. Di Battista and R. Tamassia).

S. Malitz and A. Papakostas. On the angular resolution of planar graphs. SIAM J. Discr. Math., 7:172-183, 1994.

W. Schnyder. Embedding planar graphs on the grid. In Proc. 1st ACM-SIAM Symp. Discrete Algorithms, pages 138-148, 1990.

R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16 (1987), pages 421-444.

R. Tamassia. graph Drawing. In J.E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geom., chapter 44, pages 815-832. CRC Press LLC, Boca Raton, FL, 1997.