Online Dynamic Graph Drawing
|
This paper presents an algorithm for drawing a sequence of graphs online. The algorithm strives to maintain the global structure of the graph and thus the user's mental map, while allowing arbitrary modifications between consecutive layouts. The algorithm works online and uses various execution culling methods in order to reduce the layout time and handle large dynamic graphs. Techniques for representing graphs on the GPU allow a speedup by a factor of up to 17 compared to the CPU implementation. The scalability of the algorithm across GPU generations is demonstrated. Applications of the algorithm to the visualization of discussion threads in Internet sites and to the visualization of social networks are provided.
[1] 727 Drawing Graphs: Methods and Models, M. Kaufmann and D. Wagner, eds., 2001.
[2] S.C. North, “Incremental Layout in Dynadag,” Proc. Third Int'l Symp. Graph Drawing (GD '95), pp. 409-418, 1995.
[3] S. Diehl and C. Gorg, Graphs, “They Are Changing—Dynamic Graph Drawing for a Sequence of Graphs,” LNCS 2528, pp. 23-31, 2002.
[4] K. Misue, P. Eades, W. Lai, and K. Sugiyama, “Layout Adjustment and the Mental Map,” J. Visual Languages and Computing, vol. 6, no. 2, pp. 183-210, 1995.
[5] C. Erten, P.J. Harding, S.G. Kobourov, K. Wampler, and G.V. Yee, “GraphAEL: Graph Animations with Evolving Layouts,” Proc. 11th Int'l Symp. Graph Drawing (GD '03), pp. 98-110, 2003.
[6] G. Kumar and M. Garland, “Visual Exploration of Complex Time-Varying Graphs,” IEEE Trans. Visualization and Computer Graphics, 2006.
[7] Y. Frishman and A. Tal, “Dynamic Drawing of Clustered Graphs,” Proc. IEEE Symp. Information Visualization (InfoVis '04), pp. 191-198, 2004.
[8] Y.-Y. Lee, C.-C. Lin, and H.-C. Yen, “Mental Map Preserving Graph Drawing Using Simulated Annealing,” Proc. Conf. in Research andPractice in Information Technology, vol. 60, 2006.
[9] Y. Frishman and A. Tal, “Online Dynamic Graph Drawing,” Proc.Eurographics/IEEE VGTC Symp. Visualization (EuroVis '07), pp. 75-82, 2007.
[10] I.G. Tollis, G.D. Battista, P. Eades, and R. Tamassia, Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1999.
[11] S. Hachul and M. Jünger, “An Experimental Comparison of Fast Algorithms for Drawing General Large Graphs,” Proc. 13th Int'l Symp. Graph Drawing (GD '05), pp. 235-250, 2005.
[12] C. Walshaw, “A Multilevel Algorithm for Force-Directed Graph Drawing,” J. Graph Algorithms and Applications, vol. 7, no. 3, pp.253-285, 2003.
[13] D. Harel and Y. Koren, “A Fast Multi-Scale Algorithm for Drawing Large Graphs,” J. Graph Algorithms and Applications, vol. 6, no. 3, pp. 179-202, 2002.
[14] A.J. Quigley and P. Eades, “FADE: Graph Drawing, Clustering, and Visual Abstraction,” Proc. Eighth Int'l Symp. Graph Drawing (GD '00), pp. 197-210, 2000.
[15] P. Gajer, M.T. Goodrich, and S.G. Kobourov, “A Multi-DimensionalApproach to Force-Directed Layouts of Large Graphs,” Computational Geometry, vol. 29, no. 1, pp. 3-18, 2004.
[16] S. Hachul and M. Jünger, “Drawing Large Graphs with a Potential-Field-Based Multilevel Algorithm,” Proc. 12th Int'l Symp. Graph Drawing (GD '04), pp. 285-295, 2004.
[17] Y. Koren, L. Carmel, and D. Harel, “Drawing Huge Graphs by Algebraic Multigrid Optimization,” Multiscale Modeling and Simulation, vol. 1, no. 4, pp. 645-673, 2003.
[18] D. Harel and Y. Koren, “Graph Drawing by High-Dimensional Embedding,” J. Graph Algorithms and Applications, vol. 8, no. 2, pp.195-214, 2004.
[19] U. Brandes, D. Fleischer, and T. Puppe, “Dynamic Spectral Layout of Small Worlds,” Proc. 13th Int'l Symp. Graph Drawing (GD '05), pp. 25-36, 2005.
[20] U. Brandes and D. Wagner, “A Bayesian Paradigm for Dynamic Graph Layout,” Proc. Fifth Int'l Symp. Graph Drawing (GD '97), pp.85-99, 1997.
[21] J. Moody, D. McFarland, and S. Bender-deMoll, “Dynamic Network Visualization,” Am. J. Sociology, vol. 110, no. 4, pp.1206-1241, http://www.journals.uchicago.edu/AJS/journal/ issues/v110n4/080349080349.html, 2005.
[22] C. Görg, P. Birke, M. Pohl, and S. Diehl, “Dynamic Graph Drawing of Sequences of Orthogonal and Hierarchical Graphs,” Proc. 12th Int'l Symp. Graph Drawing (GD '04), pp. 228-238, 2004.
[23] J.D. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Krüger, A.E. Lefohn, and T.J. Purcell, “A Survey of General-Purpose Computation on Graphics Hardware,” Proc. Eurographics '05, pp. 21-51, 2005.
[24] V. Pande, Folding@home on ATI GPU's, http://folding.stanford. eduFAQ-ATI.html , 2006.
[25] E. Tejada and T. Ertl, “Large Steps in GPU-Based Deformable Bodies Simulation,” Simulation Modelling Practice and Theory, vol. 13, pp. 703-715, 2005.
[26] J. Georgii, F. Echtler, and R. Westermann, “Interactive Simulation of Deformable Bodies on GPUS,” Proc. 16th Conf. Simulation and Visualization (SimVis '05), pp. 247-258, 2005.
[27] L. Nyland, M. Harris, and J. Prins, “The Rapid Evaluation of Potential Fields Using Programmable Graphics Hardware,” Proc. ACM Workshop General Purpose Computing on Graphics Hardware, 2004.
[28] I. Stephen, T. Munzner, and M. Olano, “Glimmer: Multilevel MDS on the GPU,” Technical Report UBC CS TR-2007-15, Univ. of British Columbia, 2007.
[29] T. Hakamata, T. Caudell, and E. Angel, “Force-Directed Graph Layout Using the GPU,” Proc. Supercomputing '06 Workshop “General-Purpose GPU Computing: Practice and Experience,” 2006.
[30] D. Auber and Y. Chriricota, “Improved Efficiency of Spring Embedders: Taking Advantage of GPU Programming,” Proc. Visualization, Imaging, and Image Processing Conf., pp. 169-175, 2007.
[31] Y. Frishman and A. Tal, “Multi-Level Graph Layout on the GPU,” IEEE Trans. Visualization and Computer Graphics, vol. 13, no. 6, pp.1310-1317, 2007.
[32] T.M.J. Fruchterman and E.M. Reingold, “Graph Drawing by Force-Directed Placement,” Software—Practice and Experience, vol. 21, no. 11, pp. 1129-1164, 1991.
[33] J.D. Cohen, “Drawing Graphs to Convey Proximity: An IncrementalArrangement Method,” ACM Trans. Computer-Human Interaction, vol. 4, no. 3, pp. 197-229, 1997.
[34] T. Kamada and S. Kawai, “An Algorithm for Drawing General Undirected Graphs,” Information Processing Letters, vol. 31, no. 1, pp. 7-15, 1989.
[35] T.M. Newcomb, The Acquaintance Process. Holt, Rinehart, and Winston, 1961.
[36] S. Bender-deMoll and D.A. McFarland, SoNIA—Social Network Image Animator, http://www.stanford.edu/groupsonia/, 2007.
[37] S. Bender-deMoll and D. McFarland, “The Art and Science of Dynamic Network Visualization,” J. Social Structure, vol. 7, no. 2, 2006.
[38] C. Walshaw, Graph Collection, http://staffweb.cms.gre.ac.uk/~c. walshaw partition/, 2007.
Index Terms:
Graph layout, GPU
Citation:
Yaniv Frishman, Ayellet Tal, "Online Dynamic Graph Drawing," IEEE Transactions on Visualization and Computer Graphics, vol. 14, no. 4, pp. 727-740, July/Aug. 2008, doi:10.1109/TVCG.2008.11
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb