# Similarity-Driven Edge Bundling: Data-Oriented Clutter Reduction in Graphs Layouts
## 2 Related Work  
Edge bundling is a well-known approach to reduce visual clutter in different information visualization techniques [7]. For the graph domain, the original idea was proposed by [PERSON] [11] called Hierarchical Edge Bundling (HEB). HEB employs hierarchical data to settle paths to guide the bending and grouping of edges. This is performed, drawing each edge as a B-Spline curve taking as control points a given hierarchy's intermediate points. The proposed strategy is fast since the vertices and control points are fixed during the drawing phase. However, it relies on a given hierarchy of the data and cannot be applied to scenarios where a proper hierarchy is not provided with the graph. Different approaches have been proposed to tackle this problem, avoiding the need for any other information besides graph adjacency and vertex positions to perform the bundling. One of them is the Force Directed Edge Bundling (FDEB) [10]. The FDEB creates a system of forces over the edges and executes an iterative process to bend them until the system becomes stable. Each edge is segmented into a set of points. The points are then connected, and a spring-mass system is applied, pushing and pulling these points. The Divided Edge Bundling (DEB) [12] improves the FDEB layout by separating edges with different directions, enhancing the readability for directed graphs. The major problem of force-based strategies is the computational cost. Also, they are sensitive to parameter tuning. Since they are based on optimization processes, they are prune to converge to local minima, so there is no guarantee of producing stable, visually pleasant layouts. Another group of techniques that employ only graph adjacency and the vertex positions to perform edge bundling includes the geometric-based approaches. One example is the Geometry-Based Edge Clustering (GBEC) [13]. GBEC builds a mesh based on the graph embedding and uses this mesh to bend the edges. Although a suitable solution, mesh construction is a complex process with a high computational cost. Winding Roads [14] addresses this limitation using a hybrid approach that combines QuadTree decompositions and Voronoi diagrams to discretize the visual space, speeding up the entire process. Using a point-based strategy, Moving Least Squares Edge Bundling (MLSEB) [24] first discretize the edges into points, then use moving least squares to derive control points of B-Spline curves to create the edge bundles. Similarly, LEB [25] discretizes the display space into a regular grid, then split the edges according to their directions, and, for each group of edges, uses the grid as control points of B-Splines to create the bundles. [PERSON] et al. [26] also use edges discretization but combine clustering, spline basis functions, and Functional Principal Component Analysis to bundle the edges in a statistically-controlled way. Using a different strategy, a group of techniques relies on image processing approaches to perform and improve the bundling process. The pioneer technique in this group is the Image-Based Edge Bundling (IBEB) [17]. IBEB processes an existing image of a graph to improve the visual representation of group separation. The Skeleton-Based Edge Bundling (SBEB) [18] employs a set of image processing algorithms to create paths that guide the bending of edges. The Kernel Density Estimation Edge Bundling (KDEEB) [19] draws the bundled edges using the kernel density estimation process, rendering a much faster process if compared to the previous techniques. KDEEB is then accelerated by the CUDA-based Universal Bundling (CUBu) [27] technique, taking advantage of the parallelization allowed by a GPU implementation. The Fast Fourier Transform Edge Bundling (FFTEB) [28] further improves computational speed shifting the bundling process from the image to the spectral space, allowing the processing of massive datasets defining the state-of-the-art regarding running times. In general, image-based techniques speed up considerably the bundling process.