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 classes of tested graphs and algorithms.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
The AT&T graph collection, www.graphdrawing.org
Brandenburg, F.J., Himsolt, M., Rohrer, C.: An Experimental Comparison of Force-Directed and Randomized Graph Drawing Methods. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 76–87. Springer, Heidelberg (1996)
Brandes, U., Wagner, D.: Visone - Analysis and Visualization of Social Networks. In: Graph Drawing Software. Mathematics and Visualization, vol. XII, pp. 321–340. Springer, Heidelberg (2004)
Davidson, R., Harel, D.: Drawing Graphs Nicely Using Simulated Annealing. ACM Transactions on Graphics 15(4), 301–331 (1996)
Eades, P.: A heuristic for graph drawing. Congressus Numerantium 42, 149–160 (1984)
Frick, A., Ludwig, A., Mehldau, H.: A Fast Adaptive Layout Algorithm for Undirected Graphs. In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 388–403. Springer, Heidelberg (1995)
Fruchterman, T.M.J., Reingold, E.M.: Graph Drawing by Force-directed Placement. Software–Practice and Experience 21(11), 1129–1164 (1991)
Gajer, P., Goodrich, M.T., Kobourov, S.G.: A Multi-dimensional Approach to Force-Directed Layouts of Large Graphs. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 211–221. Springer, Heidelberg (2001)
Gajer, P., Kobourov, S.G.: GRIP: Graph Drawing with Intelligent Placement. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 222–228. Springer, Heidelberg (2001)
Hachul, S.: A Potential-Field-Based Multilevel Algorithm for Drawing Large Graphs. PhD thesis, Institut für Informatik, Universität zu Köln, Germany (2005)
Hachul, S., Jünger, M.: Drawing Large Graphs with a Potential-Field-Based Multilevel Algorithm (Extended Abstract). In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 285–295. Springer, Heidelberg (2005)
Harel, D., Koren, Y.: A Fast Multi-scale Method for Drawing Large Graphs. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 183–196. Springer, Heidelberg (2001)
Harel, D., Koren, Y.: Graph Drawing by High-Dimensional Embedding. In: Goodrich, M.T., Kobourov, S.G. (eds.) GD 2002. LNCS, vol. 2528, pp. 207–219. Springer, Heidelberg (2002)
Jünger, M., Klau, G.W., Mutzel, P., Weiskircher, R.: AGD - A Library of Algorithms for Graph Drawing. In: Jünger, M., Mutzel, P. (eds.) Graph Drawing Software. Mathematics and Visualization, vol. XII, pp. 149–172. Springer, Heidelberg (2004)
Kamada, T., Kawai, S.: An Algorithm for Drawing General Undirected Graphs. Information Processing Letters 31, 7–15 (1989)
Koren, Y., Carmel, L., Harel, D.: 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
Quigley, A., Eades, P.: FADE: Graph Drawing, Clustering, and Visual Abstraction. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 197–210. Springer, Heidelberg (2001)
Tunkelang, D.: JIGGLE: Java Interactive Graph Layout Environment. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 413–422. Springer, Heidelberg (1999)
Walshaw’s, C.: Graph collection, staffweb.cms.gre.ac.uk/~c.walshaw/partition
Walshaw, C.: A Multilevel Algorithm for Force-Directed Graph Drawing. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 171–182. Springer, Heidelberg (2001)
Yusufov’s, R.: Implementation of GRIP, www.cs.arizona.edu/~kobourov/GRIP
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hachul, S., Jünger, M. (2006). An Experimental Comparison of Fast Algorithms for Drawing General Large Graphs. In: Healy, P., Nikolov, N.S. (eds) Graph Drawing. GD 2005. Lecture Notes in Computer Science, vol 3843. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11618058_22
Download citation
DOI: https://doi.org/10.1007/11618058_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-31425-7
Online ISBN: 978-3-540-31667-1
eBook Packages: Computer ScienceComputer Science (R0)