Uncluttering graph layouts using anisotropic diffusion and mass transport

Area of Science:

• Computer Science
• Graph Theory
• Data Visualization

Background:

• Graph layouts often suffer from dense areas, hindering comprehension.
• Existing visualization techniques struggle to effectively manage visual clutter in complex networks.

Purpose of the Study:

• To develop a method for reducing clutter in dense graph layout areas.
• To improve the understandability of graph visualizations without significantly altering the overall structure.

Main Methods:

• A physically inspired evolution process using a modified heat equation to generate an improved density image.
• Optimal mass transport to compute a warp field based on the density image.
• Displacing graph nodes according to the computed warp to redistribute them.

Main Results:

• The proposed technique effectively reduces clutter in dense graph regions.
• The warp preserves the graph's overall structure, minimizing mental map disturbances.
• Algorithm complexity is linear in graph size and dependent on image resolution, allowing scalability.
• Significant acceleration is achieved using graphics processing units (GPUs), enabling real-time processing of large graphs.

Conclusions:

• The method offers an effective solution for improving the clarity of dense graph layouts.
• It provides a scalable and efficient approach for graph visualization enhancement.
• The technique is applicable to various graph layout algorithms and real-world applications.