An Experimental Comparison of Fast Algorithms for Drawing General Large Graphs

Hachul, Stefan and Jünger, Michael (2006) An Experimental Comparison of Fast Algorithms for Drawing General Large Graphs. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005, Limerick, Ireland , pp. 235-250 (Official URL: http://dx.doi.org/10.1007/11618058_22).

Full text not available from this repository.

Abstract

In the last decade several algorithms that generate straight-line drawings of general large graphs have been invented.In this paper we investigate some of these methods that are based on force-directed or algebraic approaches in terms of running time and drawing quality on a big variety of artificial and real-world graphs. Our experiments indicate that there exist significant differences in drawing qualities and running times depending on the classe s of tested graphs and algorithms.

Item Type:Conference Paper
Additional Information:10.1007/11618058_22
Classifications:M Methods > M.400 Force-directed / Energy-based
M Methods > M.001 General
ID Code:694

Repository Staff Only: item control page

References

The AT&T graph collection: www.graphdrawing.org

F. J. Brandenburg, M. Himsolt, and C. Rohrer.: An Experimental Comparison of Force-Directed and Randomized Graph Drawing Methods. Graph Drawing 1995, volume 1027 of LNCS, pages 76--87. Springer-Verlag, 1996.

U. Brandes and D. Wagner.: Graph Drawing Software, volume XII of Mathematics and Visualization, chapter visone Analysis and Visualization of Social Networks, pages 321--340. Springer-Verlag, 2004.

R. Davidson and D. Harel.: Drawing Graphs Nicely Using Simulated Annealing. ACM Transactions on Graphics, 15(4):301--331, 1996.

P. Eades.: A heuristic for graph drawing. Congressus Numerantium, 42:149--160, 1984.

A. Frick, A. Ludwig, and H. Mehldau.: A Fast Adaptive Layout Algorithm for Undirected Graphs. Graph Drawing 1994, volume 894 of LNCS, pages 388--403. Springer-Verlag, 1995.

T. M. J. Fruchterman and E. M. Reingold.: Graph Drawing by Force-directed Placement. Software--Practice and Experience, 21(11):1129--1164, 1991.

P. Gajer, M. T. Goodrich, and S. G. Kobourov.: A Multi-dimensional Approach to Force-Directed Layouts of Large Graphs. Graph Drawing 2000, volume 1984 of LNCS, pages 211--221. Springer-Verlag, 2001.

P. Gajer and S. G. Kobourov.: GRIP: Graph Drawing with Intelligent Placement. Graph Drawing 2000, volume 1984 of LNCS, pages 222--228. Springer-Verlag, 2001.

S. Hachul.: A Potential-Field-Based Multilevel Algorithm for Drawing Large Graphs. PhD thesis, Institut für Informatik, Universität zu Köln, Germany, 2005.

S.Hachul and M. Jünger.: Drawing Large Graphs with a Potential-Field-Based Multilevel Algorithm (Extended Abstract). Graph Drawing 2004, volume 3383 of Lecture Notes in Computer Science, pages 285--295. Springer-Verlag, 2005.

D. Harel and Y. Koren.: A Fast Multi-scale Method for Drawing Large Graphs. Graph Drawing 2000, volume 1984 of LNCS, pages 183--196. Springer-Verlag, 2001.

D. Harel and Y. Koren.: Graph Drawing by High-Dimensional Embedding. Graph Drawing 2002, volume 2528 of LNCS, pages 207--219. Springer-Verlag, 2002.

M. Jünger, G. W. Klau, P. Mutzel, and R. Weiskircher.: Graph Drawing Software, volume XII of Mathematics and Visualization, chapter AGD - A Library of Algorithms for Graph Drawing, pages 149--172. Springer-Verlag, 2004.

T. Kamada and S. Kawai.: An Algorithm for Drawing General Undirected Graphs. Information Processing Letters, 31:7--15, 1989.

Y. Koren, L. Carmel, and D. Harel.: Drawing Huge Graphs by Algebraic Multigrid Optimization. Multiscale Modeling and Simulation, 1(4):645--673, 2003.

Y. Koren's algorithms: research.att.com/~yehuda/index_programs.html

A. Quigley and P. Eades.: FADE: Graph Drawing, Clustering, and Visual Abstraction. Graph Drawing 2000, volume 1984 of LNCS, pages 197--210. Springer-Verlag, 2001.

D. Tunkelang.: JIGGLE: Java Interactive Graph Layout Environment. Graph Drawing 1998, volume 1547 of LNCS, pages 413--422. Springer-Verlag, 1998.

C. Walshaw's graph collection: staffweb.cms.gre.ac.uk/~c.walshaw/partition

C.Walshaw.: Multilevel Algorithm for Force-Directed Graph Drawing. Graph Drawing 2000, volume 1984 of LNCS, pages 171--182. Springer-Verlag, 2001.

R. Yusufov's implementation of GRIP: www.cs.arizona.edu/~kobourov/GRIP