Curvilinear Graph Drawing Using the Force-Directed Method

Finkel, Benjamin and Tamassia, Roberto (2004) Curvilinear Graph Drawing Using the Force-Directed Method. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 448-453 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_46).

Full text not available from this repository.

Abstract

We present a method for modifying a force-directed graph drawing algorithm into an algorithm for drawing graphs with curved lines. Our method is based on embedding control points as dummy vertices so that edges can be drawn as splines. Our experiments show that our method yields aesthetically pleasing curvilinear drawing with improved angular resolution. Applying our method to the GEM algorithm on the test suite of the "Rome Graphs" resulted in an average improvement of 46% in angular resolution and of almost 6% in edge crossings.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_46
Classifications:P Styles > P.300 Curved
M Methods > M.400 Force-directed / Energy-based
ID Code:616

Repository Staff Only: item control page

References

JDSL: the data structures library in Java. http://jdsl.org.

VGJ: Visualization graphs with Java. http://www.eng.auburn.edu/department/ cse/research/graph-drawing/graph_drawing.html.

F. J. Brandenburg, M. Himsolt, and C. Rohrer. An experimental comparison of Force-directed and randomized graph drawing algorithms. In Graph drawing (Proc. GD 1995), LNCS 1027, pp. 76-87. 1996.

U. Brandes, G. Shubina, and R. Tamassia. Improving angular resolution in visualizations of geographic mnetworks. In Proc. Joint Eurographics - IEEE TCVG Symposium on Visualization (VisSym '00), pp. 23-32, 2000.

U. Brandes, G. Shubina, R. Tamassia, and D. Wagner. Fast layout methods for timetable graphs. In Graph Drawing (Proc. GD 2000), LNCS 1984, pp. 127-138, 2001.

U. Brandes and D. Wagner. Using graph layout to visualize train interconnected data. In Graph Drawing (Proc. GD 1998), LNCS 1547, pp. 44-46, 1998.

C. C. Cheng, C. A. Duncan, M. T. Goodrich, and S. G. Kobourov. Drawing planar graphs with circular arcs. In Graph Drawing (Proc. GD 1999), LNCS 1731, pp. 117-126, 1999.

R. Davidson and D. Harel. Drawing graphics nicely using simulated annealing. ACM Trans. Graph., 15(4):301-331, 1996.

D. P. Dobkin, E. R. Gansner, E. Koutsofios, and S. C. North. Implementing a general-purpose edge router. In Graph Drawing (Proc. GD 1997), LNCS 1353, pp. 262-271, 1997.

P. Eades. A heuristic for graph drawing. Congr. Numer., 42:149-160, 1984.

A. Frick, A. Ludwig, and H. Mehldau. A fast adaptive layout algorithm for undirected graphs. In Graph Drawing (Proc. GD 1994), LNCS 894, pp. 388-403, 1995.

T. Fruchterman and E. Reingold. Graph drawing by force-directed placement. Softw. - Pract. Exp., 21(11):1129-1164, 1991.

P. Gajer, M. T. Goodrich, and S. G. Kobourov. A fast multi-dimensional algorithm for drawing large graphs. Graph Drawing (Proc. GD 2000), LNCS 1984, pp. 211-221, 2000.

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.

E. R. Gansner, S. C. North, and K. P. Vo. DAG - A programm that draws directed graphs. Softw. - Pract. Exp., 18(11):1047-1062, 1988.

A. Garg and R. Tamassia. Giotto3D: A system for visualizing hierarchical structures in 3D. In Graph Drawing (Proc. GD 1996), LNCS 1190, pp. 193-200,

1997.

M. T. Goodrich and C. G. Wagner. A framework for drawing planar graphs with curves and polylines. In Graph Drawing (Proc. GD 1998), LNCS 1547, pp. 153-166, 1998.

C. Gutwenger and P. Mutzel. Planar polyline drawings with good angular resolution. In Graph Drawing (Proc. GD 1998), LNCS 1547, pp. 167-182, 1998.

D. Harel and Y. Koren. Graph drawing by high-dimensional embedding. Graph Drawing (Proc. GD 2002), LNCS 2528, pp. 207-219, 2002.

T. Kamada and S. Kawai. An algorithm for drawing general undirected graphs. Inform. Process. Lett., 31:7-15, 1989.

T. Munzner, E. Hoffman, K. Claffy, and B. Fenner. Visualizing the global topology of the MBone. In Proc. IEEE Symp. on Information Visualization, pp. 85-92, 1996.