Article

An experimental comparison of fast algorithms for drawing general large graphs

Authors:

Michael JüngerAuthors Info & Claims

GD'05: Proceedings of the 13th international conference on Graph Drawing

Pages 235 - 250

https://doi.org/10.1007/11618058_22

Published: 12 September 2005 Publication History

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.

References

[1]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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.

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

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

[21]

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

[22]

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

Cited By

Guerra-Gomez JWilson ALiu JDavies DJarvis PBier ECostabile MBuono PMatera M(2016)Network ExplorerProceedings of the International Working Conference on Advanced Visual Interfaces10.1145/2909132.2909281(108-111)Online publication date: 7-Jun-2016
https://dl.acm.org/doi/10.1145/2909132.2909281
Chaturvedi SDunne CAshktorab ZZachariah RShneiderman B(2014)Group-in-a-Box Meta-Layouts for Topological Clusters and Attribute-Based GroupsComputer Graphics Forum10.1111/cgf.1240033:8(52-68)Online publication date: 1-Dec-2014
https://dl.acm.org/doi/10.1111/cgf.12400
Huang WLin CHuang MQu HChen WCox PLiu S(2012)An aggregation-based approach to quality evaluation of graph drawingsProceedings of the 5th International Symposium on Visual Information Communication and Interaction10.1145/2397696.2397712(110-113)Online publication date: 27-Sep-2012
https://dl.acm.org/doi/10.1145/2397696.2397712
Show More Cited By

Index Terms

An experimental comparison of fast algorithms for drawing general large graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms

Recommendations

Straight-Line Drawing Algorithms for Hierarchical Graphs and Clustered Graphs
Abstract
Hierarchical graphs and clustered graphs are useful non-classical graph models for structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures. Both ...
Drawing Planar Graphs Symmetrically, III: Oneconnected Planar Graphs
Abstract
Symmetry is one of the most important aesthetic criteria in graph drawing because it reveals structure in the graph. This paper discusses symmetric drawings of oneconnected planar graphs. More specifically, we discuss planar (geometric) automorphisms, ...
Drawing Planar Graphs
WALCOM: Algorithms and Computation
Abstract
A graph is planar if it can be drawn or embedded in the plane so that no two edges intersect geometrically except at a vertex to which they are both incident. A plane graph is a planar graph with a fixed planar embedding in the plane. A drawing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

GD'05: Proceedings of the 13th international conference on Graph Drawing

September 2005

535 pages

ISBN:3540314253

Editors:
Patrick Healy
Department of Computer Science and Information Systems, University of Limerick, Ireland
,
Nikola S. Nikolov
Department of CSIS, University of Limerick, Limerick, Republic of Ireland

Sponsors

Tom Sawyer Software
sfi: sfi
Microsoft: Microsoft
Intel: Intel
DELL

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 12 September 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Guerra-Gomez JWilson ALiu JDavies DJarvis PBier ECostabile MBuono PMatera M(2016)Network ExplorerProceedings of the International Working Conference on Advanced Visual Interfaces10.1145/2909132.2909281(108-111)Online publication date: 7-Jun-2016
https://dl.acm.org/doi/10.1145/2909132.2909281
Chaturvedi SDunne CAshktorab ZZachariah RShneiderman B(2014)Group-in-a-Box Meta-Layouts for Topological Clusters and Attribute-Based GroupsComputer Graphics Forum10.1111/cgf.1240033:8(52-68)Online publication date: 1-Dec-2014
https://dl.acm.org/doi/10.1111/cgf.12400
Huang WLin CHuang MQu HChen WCox PLiu S(2012)An aggregation-based approach to quality evaluation of graph drawingsProceedings of the 5th International Symposium on Visual Information Communication and Interaction10.1145/2397696.2397712(110-113)Online publication date: 27-Sep-2012
https://dl.acm.org/doi/10.1145/2397696.2397712
Sallaberry AMuelder CMa K(2012)Clustering, visualizing, and navigating for large dynamic graphsProceedings of the 20th international conference on Graph Drawing10.1007/978-3-642-36763-2_43(487-498)Online publication date: 19-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-36763-2_43
Shneiderman BDunne C(2012)Interactive network exploration to derive insightsProceedings of the 20th international conference on Graph Drawing10.1007/978-3-642-36763-2_2(2-18)Online publication date: 19-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-36763-2_2
Kamamura SKoizumi YMiyamura TArakawa SShiomoto KMurata MChemouil PMehaoua AFestor OLupu E(2011)Control and visualization system for managed self-organization networkProceedings of the 7th International Conference on Network and Services Management10.5555/2147671.2147734(358-361)Online publication date: 24-Oct-2011
https://dl.acm.org/doi/10.5555/2147671.2147734
Boschetti ASalgarelli LMuelder CMa K(2011)TViProceedings of the 8th International Symposium on Visualization for Cyber Security10.1145/2016904.2016905(1-10)Online publication date: 20-Jul-2011
https://dl.acm.org/doi/10.1145/2016904.2016905
Mozhayskiy VMiller BMa KTagkopoulos ITowns JBrown SKatz D(2011)A scalable multi-scale framework for parallel simulation and visualization of microbial evolutionProceedings of the 2011 TeraGrid Conference: Extreme Digital Discovery10.1145/2016741.2016749(1-8)Online publication date: 18-Jul-2011
https://dl.acm.org/doi/10.1145/2016741.2016749
Eades PGutwenger CHong SMutzel P(2010)Graph drawing algorithmsAlgorithms and theory of computation handbook10.5555/1882723.1882729(6-6)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1882723.1882729
Dwyer T(2009)Scalable, versatile and simple constrained graph layoutProceedings of the 11th Eurographics / IEEE - VGTC conference on Visualization10.5555/2421899.2421943(991-1006)Online publication date: 10-Jun-2009
https://dl.acm.org/doi/10.5555/2421899.2421943
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents