A Quantitative Comparison of Stress-Minimization Approaches for Offline Dynamic Graph Drawing

Brandes, Ulrik and Mader, Martin (2012) A Quantitative Comparison of Stress-Minimization Approaches for Offline Dynamic Graph Drawing. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 99-110 (Official URL: http://dx.doi.org/ 10.1007/978-3-642-25878-7_11).

Full text not available from this repository.

Abstract

In dynamic graph drawing, the input is a sequence of graphs for which a sequence of layouts is to be generated such that the quality of individual layouts is balanced with layout stability over time. Qualitatively different extensions of drawing algorithms for static graphs to the dynamic case have been proposed, but little is known about their relative utility. We report on a quantitative study comparing the three prototypical extensions via their adaptation for the stress-minimization framework. While some findings are more subtle, the linking approach connecting consecutive instances of the same vertex is found to be the overall method of choice.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-25878-7_11
Classifications:M Methods > M.100 Algebraic
P Styles > P.999 Others
ID Code:1245

Repository Staff Only: item control page

References

Böhringer, K.F., Paulisch, F.N.: Using constraints to achieve stability in automatic graph layout algorithms. In: Proc. of the SIGCHI Conference on Human Factors in Computing Systems (CHI 1990), pp. 43–51. ACM (1990)

Brandes, U., Corman, S.R.: Visual unrolling of network evolution and the analysis of dynamic discourse. Information Visualization 2(1), 40–50 (2003)

Brandes, U., Pich, C.: An Experimental Study on Distance-Based Graph Drawing. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 218–229. Springer, Heidelberg (2009)

Brandes, U., Wagner, D.: A Bayesian Paradigm for Dynamic Graph Layout. In: DiBattista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 236–247. Springer, Heidelberg (1997)

Branke, J.: Dynamic Graph Drawing. In: Kaufmann, M., Wagner, D. (eds.) Drawing Graphs. LNCS, vol. 2025, pp. 228–246. Springer, Heidelberg (2001)

Bridgeman, S.S., Tamassia, R.: Difference metrics for interactive orthogonal graph drawing algorithms. Journal of Graph Algorithms and Applications 4(3), 47–74 (2000)

Diehl, S., Görg, C.: Graphs, they are Changing. In: Goodrich, M.T., Kobourov,S.G. (eds.) GD 2002. LNCS, vol. 2528, pp. 23–30. Springer, Heidelberg (2002)

Erten, C., Harding, P., Kobourov, S., Wampler, K., Yee, G.: Graphael: Graph Animations with Evolving Layouts. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 98–110. Springer, Heidelberg (2004)

Erten, C., Kobourov, S., Le, V., Navabi, A.: Simultaneous graph drawing: Layout algorithms and visualization schemes. Journal of Graph Algorithms and Applications 9(1), 165–182 (2005)

Gansner, E., Koren, Y., North, S.: Graph Drawing by Stress Majorization. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 239–250. Springer, Heidelberg (2005)

Gilbert, E.N.: Random graphs. The Annals of Mathematical Statistics 30(4), 1141–1144 (1959)

Huang, M.L., Eades, P., Wang, J.: On-line animated visualization of huge graphs using a modified spring algorithm. Journal of Visual Languages and Computing 9(6), 623–645 (1998)

Kamada, T., Kawai, S.: An algorithm for drawing general undirected graphs. Information Processing Letters 31, 7–15 (1989)

Michell, L., Amos, A.: Girls, pecking order and smoking. Social Science & Medicine 44(12), 1861–1869 (1997)

Misue, K., Eades, P., Lai, W., Sugiyama, K.: Layout adjustment and the mental map. Journal on Visual Languages and Computing 6(2), 183–210 (1995)

Moody, J., McFarland, D.A., Bender-deMoll, S.: Dynamic Network Visualization. American Journal of Sociology 110(4), 1206–1241 (2005)

North, S.C.: Incremental Layout with DynaDag. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 409–418. Springer, Heidelberg (1996)

Purchase, H.C., Samra, A.: Extremes are Better: Investigating Mental Map Preservation in Dynamic Graphs. In: Stapleton, G., Howse, J., Lee, J. (eds.) Diagrams 2008. LNCS (LNAI), vol. 5223, pp. 60–73. Springer, Heidelberg (2008)

Robins, G., Pattison, P., Kalish, Y., Lusher, D.: An introduction to exponential random graph (p*) models for social networks. social networks 29(2), 173–191 (2007)

Sibson, R.: Studies in the robustness of multidimensional scaling: Procrustes statistics. Journal of the Royal Statistical Society. Series B (Methodological) 40(2), 234–238 (1978)

Snijders, T.A.B.: The statistical evaluation of social network dynamics. Sociological Methodology 31, 361–395 (2001)

Van De Bunt, G.G., Van Duijn, M.A., Snijders, T.A.: Friendship networks through time: An actor-oriented dynamic statistical network model. Computational & Mathematical Organization Theory 5, 167–192 (1999)