This paper presents a graph bundling algorithm that agglomerates edges taking into account both spatial proximity as well as user-defined criteria in order to reveal patterns that were not perceivable with previous bundling techniques. Each edge belongs to a group that may either be an input of the problem or found by clustering one or more edge properties such as origin, destination, orientation, length or domain-specific properties. Bundling is driven by a stack of density maps, with each map capturing both the edge density of a given group as well as interactions with edges from other groups. Density maps are efficiently calculated by smoothing 2D histograms of edge occurrence using repeated averaging filters based on integral images. A CPU implementation of the algorithm is tested on several graphs, and different grouping criteria are used to illustrate how the proposed technique can render different visualizations of the same data. Bundling performance is much higher than on previous approaches, being particularly noticeable on large graphs, with millions of edges being bundled in seconds.
proposed Geometry Based Edge Bundling (GBEB) @cite_0 , one of the first methods suitable for bundling general undirected layouts. Bundling is performed by forcing edges to pass through the same control points of a control mesh. Holten and van Wijk used principles of physics to attract edges that are close to each other in their Force-directed edge bundling (FDEB) algorithm @cite_28 . Bundled graphs were considered to be smoother and easier to read than on previous approaches, but the computational complexity of the algorithm is high, making it slower than GBEB. FDEB was later extended to separate opposite-direction bundles in directed graphs in the Divided Edge Bundling (DEB) algorithm @cite_13 . Control meshes were revisited in the Wind Roads (WR) algorithm proposed by @cite_9 . In WR, graph edges are routed along mesh edges using a shortest path algorithm. The computational performance of the algorithm was better than FDEB and comparable to GBEB. Later, extended the algorithm to 3D @cite_14 .
@cite_14 @cite_28 @cite_9 @cite_0 @cite_13
2132907133 2068261792 1982799219 1793674997
The node-link diagram is an intuitive and venerable way to depict a graph. To reduce clutter and improve the readability of node-link views, Holten & van Wijk's force-directed edge bundling employs a physical simulation to spatially group graph edges. While both useful and aesthetic, this technique has shortcomings: it bundles spatially proximal edges regardless of direction, weight, or graph connectivity. As a result, high-level directional edge patterns are obscured. We present divided edge bundling to tackle these shortcomings. By modifying the forces in the physical simulation, directional lanes appear as an emergent property of edge direction. By considering graph topology, we only bundle edges related by graph structure. Finally, we aggregate edge weights in bundles to enable more accurate visualization of total bundle weights. We compare visualizations created using our technique to standard force-directed edge bundling, matrix diagrams, and clustered graphs; we find that divided edge bundling leads to visualizations that are easier to interpret and reveal both familiar and previously obscured patterns. Visualizing graphs containing many nodes and edges efficiently is quite challenging. Drawings of such graphs generally suffer from visual clutter induced by the large amount of edges and their crossings. Consequently, it is difficult to read the relationships between nodes and the high-level edge patterns that may exist in standard nodelink diagram representations. Edge bundling techniques have been proposed to help solve this issue, which rely on high quality edge rerouting. In this paper, we introduce an intuitive edge bundling technique which efficiently reduces edge clutter in graphs drawings. Our method is based on the use of a grid built using the original graph to compute the edge rerouting. In comparison with previously proposed edge bundling methods, our technique improves both the level of clutter reduction and the computation performance. The second contribution of this paper is a GPU-based rendering method which helps users perceive bundles densities while preserving edge color. Graphs are often used to encapsulate relationships between objects. Node-link diagrams, commonly used to visualize graphs, suffer from visual clutter on large graphs. Edge bundling is an effective technique for alleviating clutter and revealing high-level edge patterns. Previous methods for general graph layouts either require a control mesh to guide the bundling process, which can introduce high variation in curvature along the bundles, or all-to-all force and compatibility calculations, which is not scalable. We propose a multilevel agglomerative edge bundling method based on a principled approach of minimizing ink needed to represent edges, with additional constraints on the curvature of the resulting splines. The proposed method is much faster than previous ones, able to bundle hundreds of thousands of edges in seconds, and one million edges in a few minutes. We propose a new approach to edge bundling. At the first stage we route the edge paths so as to minimize a weighted sum of the total length of the paths together with their ink. As this problem is NP-hard, we provide an efficient heuristic that finds an approximate solution. The second stage then separates edges belonging to the same bundle. To achieve this, we provide a new and efficient algorithm that solves a variant of the metro-line crossing minimization problem. The method creates aesthetically pleasing edge routes that give an overview of the global graph structure, while still drawing each edge separately, without intersecting graph nodes, and with few crossings.