Graph Drawing by Stress Majorization

Gansner, Emden R. and Koren, Yehuda and North, Stephen (2004) Graph Drawing by Stress Majorization. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 239-250 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_25).

Full text not available from this repository.

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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_25
Classifications:M Methods > M.400 Force-directed / Energy-based
P Styles > P.720 Straight-line
ID Code:591

Repository Staff Only: item control page

References

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

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.

J. De Leeuw, "Convergence of the Majorization Method for Multidimensional Scaling", Journal of Classification 5 (1988), pp. 163-180.

G. Di Battista, P. Eades, R. Tamassia and I. G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice-Hall, 1999.

I. Borg and P. Groenen, Modern Multidimensional Scalling: Theory and Applications, Springer-Verlag, 1997.

J. D. Cohen, "Drawing Graphs to Convey Proximity: an Incremental Arrangement Method", ACM Transactions on Computer-Human Interaction 4 (1997), pp. 197-229.

E. R. Gansner and S. C. North, "Improved force-directed layouts", Proceedings of Graph Drawing '98, LNCS 1547, pp. 364-373, Springer-Verlag, 1998.

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.

G. H. Golub and C. F. Van Loan, Matrix Computations, John Hopkins University Press, 1996.

R. Hadany and D. Harel, "A Multi-Scale Method for DRawing Graphs Nicely", Discrete Applied Mathematics 113 (2001), pp. 3-21.

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.

D. Harel and Y. Koren, "Graph DRawing by High-Dimensional Embedding", Proceedings of Graph Drawing 2002, LNCS 2528, pp. 207-219, Springer-Verlag, 2002.

D. Harel and Y. Koren, ""Axis-by-Axis Stress Minimization", Proceedings of Graph DRawing 2003, Springer-Verlag, pp. 450-459, 2003.

Y. Koren, "Graph Drawing by Subspace Optimization", Proceedings 6th Joint Eurographics - IEEE TCVG Symposium Visualization (VisSym '04), pp. 65-74, Eurographics, 2004.

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

M. Kaufmann and D. Wagner (Eds.), Drawing Graphs: Methods and Models, LNCS 2025, Springer-Verlag, 2001.

J. Kruskal and J. Seery, "Designing network diagrams", Proceedings First General Conference on Social Graphics (1980), pp. 22-50.

J. W. Sammon, "A Nonlinear Mapping for Data Structure Analysis", IEEE Trans. on Computers 18 (1969), pp. 401-409.

C. Walshaw, "A Multilevel Algorithm for Force-Directed Graph Drawing", Proceedings 8th Graph Drawing (GD'00), LNCS 1984, pp. 171-182, Springer-Verlag, 2000.

Graphviz. www.research.att.com/sw/tools/graphviz/

Graphlet. www.infosun.fmi.uni-passau.de/Graphlet/

Intel Math Kernel Library. www.intel.com/software/products/mkl

Automatically Tuned Linear Algebra Software (ATLAS). math-atlas.sourceforge.net/