An Incremental Layout Method for Visualizing Online Dynamic Graphs

Crnovrsanin, Tarik and Chu, Jacqueline and Ma, Kwan-Liu (2015) An Incremental Layout Method for Visualizing Online Dynamic Graphs. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015, Los Angeles, CA, USA , pp. 16-29 (Official URL:

Full text not available from this repository.


Graphs provide a visual means for examining relation data and force-directed methods are often used to lay out graphs for viewing. Making sense of a dynamic graph as it evolves over time is challenging, and previous force-directed methods were designed for static graphs. In this paper, we present an incremental version of a multilevel multi-pole layout method with a refinement scheme incorporated, which enables us to visualize online dynamic networks while maintaining a mental map of the graph structure. We demonstrate the effectiveness of our method and compare it to previous methods using several network data sets.

Item Type:Conference Paper
Classifications:M Methods > M.300 Dynamic / Incremental / Online
M Methods > M.400 Force-directed / Energy-based
ID Code:1473

Repository Staff Only: item control page


Archambault, D., Purchase, H.C., Pinaud, B.: Animation, small multiples, and the effect of mental map preservation in dynamic graphs. IEEE Trans. Vis. Comput. Graph. 17(4), 539–552 (2011)

Bach, B., Pietriga, E., Fekete, J.D.: GraphDiaries: animated transitions and temporal navigation for dynamic networks. IEEE Trans. Vis. Comput. Graph. 20(5), 740–754 (2014)

Boitmanis, K., Brandes, U., Pich, C.: Visualizing internet evolution on the autonomous systems level. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 365–376. Springer, Heidelberg (2008)

Brandes, U., Fleischer, D., Puppe, T.: Dynamic spectral layout of small worlds. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 25–36. Springer, Heidelberg (2006)

Brandes, U., Mader, M.: A quantitative comparison of stress-minimization approaches for offline dynamic graph drawing. In: Speckmann, B. (ed.) GD 2011. LNCS, vol. 7034, pp. 99–110. Springer, Heidelberg (2011)

Brandes, U., Wagner, D.: A bayesian paradigm for dynamic graph layout. In: Di Battista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 236–247. Springer, Heidelberg (1997)

Che, L., Liang, J., Yuan, X., Shen, J., Xu, J., Li, Y.: Laplacian-based dynamic graph visualization. In: Visualization Symposium (PacificVis), 2015 IEEE Pacific, pp. 69–73 (2015)

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

Erten, C., Harding, P.J., Kobourov, S.G., 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)

Frishman, Y., Tal, A.: Online dynamic graph drawing. IEEE Trans. Vis. Comput. Graph. 14(4), 727–740 (2008)

Godiyal, A., Hoberock, J., Garland, M., Hart, J.C.: Rapid multipole graph drawing on the GPU. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 90–101. Springer, Heidelberg (2009)

Gorochowski, T., di Bernardo, M., Grierson, C.: Using aging to visually uncover evolutionary processes on networks. IEEE Trans. Vis. Comput. Graph. 18(8), 1343–1352 (2012)

Hachul, S., Jünger, M.: An experimental comparison of fast algorithms for drawing general large graphs. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 235–250. Springer, Heidelberg (2006)

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)

Hu, Y., Kobourov, S.G., Veeramoni, S.: Embedding, clustering and coloring for dynamic maps. In: Visualization Symposium (PacificVis), 2012 IEEE Pacific, pp. 33–40 (2012)

Khoury, M., Hu, Y., Krishnan, S., Scheidegger, C.: Drawing large graphs by low-rank stress majorization. Comput. Graph. Forum 31(3pt1), 975–984 (2012)

Koren, Y., Carmel, L., Harel, D.: Drawing huge graphs by algebraic multigrid optimization. Multiscale Model. Simul. 1, 645–673 (2003)

Kumar, G., Garland, M.: Visual exploration of complex time-varying graphs. IEEE Trans. Vis. Comput. Graph. 12(5), 805–812 (2006)

Lee, Y.Y., Lin, C.C., Yen, H.C.: Mental map preserving graph drawing using simulated annealing. In: Proceedings of the 2006 Asia-Pacific Symposium on Information Visualisation, APVis 2006, Vol. 60, pp. 179–188 (2006)

Mcfarland, D.: Student resistance: how the formal and informal organization of classrooms facilitate everyday forms of student defiance. Am. J. Sociol. 107(3), 612–678 (2001)

Misue, K., Eades, P., Lai, W., Sugiyama, K.: Layout adjustment and the mental map. J. Vi. Lang. Comput. 6(2), 183–210 (1995)

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

Purchase, H.C., Hoggan, E., Görg, C.: How important is the “Mental Map”? – an empirical investigation of a dynamic graph layout algorithm. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 184–195. Springer, Heidelberg (2007)

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)

Tufte, E.R.: Envisioning Information. Graphic Press, Cheshire (1990)

Yao, Y.: Collection and streaming of graph datasets. http://​www.​eecs.​wsu.​edu/​yyao/​StreamingGraphs.​html