Abstract:

Many graph layouts include very dense areas, making the layout difficult to understand. In this paper, we propose a technique for modifying an existing layout in order to reduce the clutter in dense areas. A physically-inspired evolution process, based on a modified heat equation is used to create an improved layout density image, making better use of available screen space. Using results from optimal mass transport problems, a warp to the improved density image is computed. The graph nodes are displaced according to the warp. The warp maintains the overall structure of the graph, thus limiting disturbances to the mental map, while reducing the clutter in dense areas of the layout. The complexity of the algorithm depends mainly on the resolution of the image visualizing the graph and is linear in the size of the graph. This allows scaling the computation according to required running times. It is demonstrated how the algorithm can be significantly accelerated using a graphics processing unit (GPU), resulting in the ability to handle large graphs in a matter of seconds. Results on several layout algorithms and applications are demonstrated.

(Yaniv Frishman, Ayellet Tal, “Uncluttering Graph Layouts Using Anisotropic Diffusion and Mass Transport”, IEEE Transactions on Visualization and Computer Graphics, vol. 15, no. 5, pp. 777-788, Sep./Oct. 2009)

Ke-Sen Huang has assembled a web page with links to all papers presented at these two important conferences, High Performance Graphics (a synthesis of the Graphics Hardware and Interactive Ray Tracing conferences) and SIGGRAPH. Both conferences had quite a number of GPGPU-related publications.  Highlights from HPG include a paper on computing minimum spanning trees on the GPU, one on optimizing stream compaction on GPUs, and a study from NVIDIA on understanding the efficiency of GPUs and of wide-SIMD architectures in general on inherently imbalanced workloads like ray tracing (among others).

Click here for SIGGRAPH papers, and here for HPG papers. Ke-Sen’s pages are also a good resource for other conferences in the field.

A graph is an ordered pair G=(V,E) where V is a set of nodes and E is a set of edges connecting nodes. Graph drawing addresses the problem of creating geometric representations of graphs. Unlike matrices or images, graphs are unstructured and hence graph layout may not seem to be suitable for acceleration on the GPU. These papers present two GPU-accelerated graph drawing algorithms which are able to quickly compute aesthetic layouts of large graphs. One is for the layout of a single graph and the other is for computing stable layouts of a sequence of graphs. Speedups of 5.5x to 17x relative to a CPU implementation are demonstrated. (Yaniv Frishman and Ayellet Tal, Multi-Level Graph Layout on the GPU, IEEE Transactions on Visualization and Computer Graphics (Proceedings Information Visualization 2007), 13(6):1310-1317, 2007)
(Yaniv Frishman and Ayellet Tal, Online Dynamic Graph Drawing, accepted to IEEE Transactions on Visualization and Computer Graphics)