creators_name: Gansner, Emden R.
creators_name: Koren, Yehuda
creators_name: North, Stephen
editors_name: Pach, János
editors_id: Pach, János
type: confpaper
datestamp: 2005-07-19
lastmod: 2008-09-18 11:08:54
metadata_visibility: show
title: Graph Drawing by Stress Majorization
ispublished: pub
subjects: M.400
subjects: P.720
full_text_status: none
abstract: One of the most popular graph drawing methods is based on achieving graph-theoretic target distances. This method was used by Kamada and Kawai [15], who formulated it as an energy optimization problem. Their energy is known in the multidimensional scaling (MDS) community as the stress function. In this work, we show how to draw graphs by stress majorization, adapting a technique known in the MDS community for more than two decades. It appears that majorization has advantages over the technique of Kamada and Kawai in running time and stability. We also found the majorization-based optimization being essential to a few extensions to the basic energy model. These extensions can improve layout quality and computation speed in practice.
date: 2004
date_type: published
publisher: Springer
pagerange: 239-250
refereed: FALSE
referencetext: 1. R. F. Boisvert et al., "The Matrix Market: A web resource for test matrix collections", in Quality of Numerical Software, Assessment and Enhancement, R. F. Boisvert, ed., Chapman Hall, 1997, pp. 125-137. math.nist.gov/MatrixMarket
2. F. J. Brandenburg, M. Himsolt and C. Rohrer, "An Experimental Comparison of Force-Directed and Randomized Graph Drawing Algorithms", Proceedings of Graph Drawing'95, LNCS1027, pp. 76-87, Springer Verlag, 1995.
3. J. De Leeuw, "Convergence of the Majorization Method for Multidimensional Scaling", Journal of Classification 5 (1988), pp. 163-180.
4. G. Di Battista, P. Eades, R. Tamassia and I. G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice-Hall, 1999.
5. I. Borg and P. Groenen, Modern Multidimensional Scalling: Theory and Applications, Springer-Verlag, 1997.
6. J. D. Cohen, "Drawing Graphs to Convey Proximity: an Incremental Arrangement Method", ACM Transactions on Computer-Human Interaction 4 (1997), pp. 197-229.
7. E. R. Gansner and S. C. North, "Improved force-directed layouts", Proceedings of Graph Drawing '98, LNCS 1547, pp. 364-373, Springer-Verlag, 1998.
8. P. Gajer, M. T. Goodrich and S. G. Kobourov, "A Multi-dimensional Approach to Force-Directed Layouts of Large Graphs", Proceedings of Graph Drawing 2000, LNCS 1984, pp. 211-221, Springer-Verlag, 2000.
9. G. H. Golub and C. F. Van Loan, Matrix Computations, John Hopkins University Press, 1996.
10. R. Hadany and D. Harel, "A Multi-Scale Method for DRawing Graphs Nicely", Discrete Applied Mathematics 113 (2001), pp. 3-21.
11. D. Harel and Y. Koren, "A Fast Multi-Scale Method for Drawing Large Graphs", Journal of GRaph Algorithms and Applications 6 (2002), pp. 179-202.
12. D. Harel and Y. Koren, "Graph DRawing by High-Dimensional Embedding", Proceedings of Graph Drawing 2002, LNCS 2528, pp. 207-219, Springer-Verlag, 2002.
13. D. Harel and Y. Koren, ""Axis-by-Axis Stress Minimization", Proceedings of Graph DRawing 2003, Springer-Verlag, pp. 450-459, 2003.
14. Y. Koren, "Graph Drawing by Subspace Optimization", Proceedings 6th Joint Eurographics - IEEE TCVG Symposium Visualization (VisSym '04), pp. 65-74, Eurographics, 2004.
15. T. Kamada and S. Kawai, "An Algorithm for Drawing General Undirected Graphs", Information Processing Letters 31 (1989), pp. 7-15.
16. M. Kaufmann and D. Wagner (Eds.), Drawing Graphs: Methods and Models, LNCS 2025, Springer-Verlag, 2001.
17. J. Kruskal and J. Seery, "Designing network diagrams", Proceedings First General Conference on Social Graphics (1980), pp. 22-50.
18. J. W. Sammon, "A Nonlinear Mapping for Data Structure Analysis", IEEE Trans. on Computers 18 (1969), pp. 401-409.
19. C. Walshaw, "A Multilevel Algorithm for Force-Directed Graph Drawing", Proceedings 8th Graph Drawing (GD'00), LNCS 1984, pp. 171-182, Springer-Verlag, 2000.
20. Graphviz. www.research.att.com/sw/tools/graphviz/
21. Graphlet. www.infosun.fmi.uni-passau.de/Graphlet/
22. Intel Math Kernel Library. www.intel.com/software/products/mkl
23. Automatically Tuned Linear Algebra Software (ATLAS). math-atlas.sourceforge.net/

citation: Gansner, Emden R. and Koren, Yehuda and North, Stephen (2004) Graph Drawing by Stress Majorization. [Conference Paper]