Uncluttering Graph Layouts Using Anisotropic Diffusion and Mass Transport

Yaniv Frishman, Ayellet Tal
Department of Computer Science, Technion – Israel Institute of Technology, Haifa, Israel
IEEE Transactions on Visualization and Computer Graphics, 2009


   title={Uncluttering graph layouts using anisotropic diffusion and mass transport},

   author={Frishman, Y. and Tal, A.},

   journal={IEEE Transactions on Visualization and Computer Graphics},



   publisher={Published by the IEEE Computer Society}


Download Download (PDF)   View View   Source Source   



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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2020 hgpu.org

All rights belong to the respective authors

Contact us: