This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Multi-Level Graph Layout on the GPU
November/December 2007 (vol. 13 no. 6)
pp. 1310-1319
Ayellet Tal, IEEE Computer Society
This paper presents a new algorithm for force directed graph layout on the GPU. The algorithm, whose goal is to compute layouts accurately and quickly, has two contributions. The first contribution is proposing a general multi-level scheme, which is based on spectral partitioning. The second contribution is computing the layout on the GPU. Since the GPU requires a data parallel programming model, the challenge is devising a mapping of a naturally unstructured graph into a well-partitioned structured one. This is done by computing a balanced partitioning of a general graph. This algorithm provides a general multi-level scheme, which has the potential to be used not only for computation on the GPU, but also on emerging multi-core architectures. The algorithm manages to compute high quality layouts of large graphs in a fraction of the time required by existing algorithms of similar quality. An application for visualization of the topologies of ISP (Internet Service Provider) networks is presented.

[1] Rocketfuel maps and data. http://www.cs.washington.edu/-research/networking rocketfuel/.
[2] J. Barnes and P. Hut, A hierarchical O(N logN) force-calculation algorithm. Nature, 324 (4): 446–449, 1986.
[3] I. Buck, T. Foley, D. Horn, J. Sugerman, K. Fatahalian, M. Houston, and P. Hanrahan, Brook for GPUs: stream computing on graphics hardware. ACM Trans. on Graphics, 23 (3): 777–786, 2004.
[4] F. R. K. Chung, Spectral graph theory. Regional Conference Series in Mathematics, American Mathematical Society, 92: 1–212, 1997.
[5] R. Fernando editor. GPU Gems: Programming Techniques, Tips, and Tricks for Real-Time Graphics. 2004.
[6] M. Fiedler, A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czechoslovak Mathematical Journal, 25 (100): 619–633, 1975.
[7] Y. Frishman and A. Tal, Online dynamic graph drawing. In EuroVis, pages 75–82, 2007.
[8] T. M. J. Fruchterman and E. M. Reingold, Graph drawing by force-directed placement. Software—Practice and Experience, 21 (11): 1129–1164, 1991.
[9] P. Gajer, M. T. Goodrich, and S. G. Kobourov, A multi-dimensional approach to force-directed layouts of large graphs. Comput. Geom, 29 (1): 3–18, 2004.
[10] N. Galoppo, N. K. Govindaraju, M. Henson, and D. Manocha, LU-GPU: Efficient algorithms for solving dense linear systems on graphics hardware. In ACM / IEEE Supercomputing, 2005.
[11] E. R. Gansner, Y. Koren, and S. C. North, Topological fisheye views for visualizing large graphs. IEEE Transactions on Visualization and Computer Graphics, 11 (4): 457–468, 2005.
[12] J. Georgii, F. Echtler, and R. Westermann, Interactive simulation of deformable bodies on GPUs. In SimVis, pages 247–258, 2005.
[13] N. Goodnight, C. Woolley, G. Lewin, D. Luebke, and G. Humphreys, A multigrid solver for boundary value problems using programmable graphics hardware. In SIGGRAPH/Eurographics Workshop on Graphics Hardware, pages 102–111, 2003.
[14] GPGPU. http:/www.gpgpu.org.
[15] S. Hachul and M. Jünger, Drawing large graphs with a potential-field-based multilevel algorithm. In Graph Drawing, pages 285–295, 2004.
[16] S. Hachul and M. Jünger, An experimental comparison of fast algorithms for drawing general large graphs. In Graph Drawing, volume 3843 of LNCS pages 235–250, 2005.
[17] C. D. Hansen, J. M. Kniss, A. E. Lefohn, and R. T. Whitaker, A streaming narrow-band algorithm: Interactive computation and visualization of level sets. IEEE Transactions on Visualization and Computer Graphics, 10 (4): 422–433, 2004.
[18] D. Harel and Y. Koren, A Fast Multi-Scale Algorithm for Drawing Large Graphs. J. Graph Algorithms Appl., 6 (3): 179–202, 2002.
[19] D. Harel and Y. Koren, Drawing graphs with non-uniform vertices. In Proc. Working Conference on Advanced Visual Interfaces (AVI'02), pages 157–166. ACM Press, 2002.
[20] D. Harel and Y. Koren, Graph drawing by high-dimensional embedding. J. Graph Algorithms Appl, 8 (2): 195–214, 2004.
[21] M. J. Harris, W. Baxter, T. Scheuermann, and A. Lastra, Simulation of cloud dynamics on graphics hardware. In SIGGRAPH/Eurographics Workshop on Graphics Hardware, pages 92–101, 2003.
[22] T. Jansen, B. von Rymon-Lipinski, N. Hanssen, and E. Keeve, Fourier volume rendering on the GPU using a split-stream-FFT. In Vision, modeling and visualization, pages 395–403, 2004.
[23] T. Kamada and S. Kawai, An algorithm for drawing general undirected graphs. Information Processing Letters, 31 (1): 7–15, 1989.
[24] M. Kaufmann and D. Wagner editors. Drawing Graphs: Methods and Models. 2001.
[25] P. Kipfer, M. Segal, and R. Westermann, Uberflow A GPU-based particle engine. In Eurographics/SIGGRAPH Workshop on Graphics Hardware, pages 115–122, 2004.
[26] Y. Koren, L. Carmel, and D. Harel, Drawing huge graphs by algebraic multigrid optimization. Multiscale Modeling & Simulation, 1 (4): pages 645–673, 2003.
[27] J. Krüger and R. Westermann, Linear algebra operators for GPU implementation of numerical algorithms. In Proc. ACM SIGGRAPH, volume 22 (3) of ACM Transactions on Graphics, pages 908–916, 2003.
[28] Y. Liu, X. Liu, and E. Wu, Real-time 3D fluid simulation on GPU with complex obstacles. In Pacific Conference on Computer Graphics and Applications, pages 247–256, 2004.
[29] K. Moreland and E. Angel, The FFT on a GPU. In SIGGRAPH/Eurographics Workshop on Graphics Hardware, pages 112–119, 2003.
[30] L. Nyland, M. Harris, and J. Prins, The rapid evaluation of potential fields using programmable graphics hardware. In ACM Workshop on General Purpose Computing on Graphics Hardware, 2004.
[31] 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. In Eurographics, pages 21–51, 2005.
[32] M. Pharr and R. Fernando editors. GPU Gems 2 : Programming Techniques for High-Performance Graphics and General-Purpose Computation. 2005.
[33] PothenA., SimonH., and LiouK, Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. and Appl., 11: 430–452, 1990.
[34] A. J. Quigley and P. Eades, FADE: Graph drawing, clustering, and visual abstraction. In Graph Drawing, number 1984 in LNCS, pages 197–210, 2000.
[35] J. Shi and J. Malik, Normalized cuts and image segmentation. IEEE Trans. on PAMI, 22 (8): 888–905, 2000.
[36] N. T. Spring, R. Mahajan, and D. Wetherall, Measuring ISP topologies with rocketfuel. In SIGCOMM, pages 133–145, 2002.
[37] E. Tejada and T. Ertl, Large Steps in GPU-based Deformable Bodies Simulation. Simulation Modelling Practice and Theory, 13: 703–715, 2005.
[38] I. G. Tollis, G. D. Battista, P. Eades, and R. Tamassia, Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1999.
[39] C. Walshaw graph collection. http://staffweb.cms.gre.ac.-uk/~c.walshaw partition/.
[40] C. Walshaw, A Multilevel Algorithm for Force-Directed Graph Drawing. J. Graph Algorithms Appl., 7 (3): 253–285, 2003.
[41] D. S. Watkins, Fundamentals of Matrix Computations. John Wiley, 2002.

Index Terms:
Graph layout, GPU, graph partitioning.
Citation:
Yaniv Frishman, Ayellet Tal, "Multi-Level Graph Layout on the GPU," IEEE Transactions on Visualization and Computer Graphics, vol. 13, no. 6, pp. 1310-1319, Nov.-Dec. 2007, doi:10.1109/TVCG.2007.70580
Usage of this product signifies your acceptance of the Terms of Use.