# Similarity-Driven Edge Bundling: Data-Oriented Clutter Reduction in Graphs Layouts
## 1 Introduction  
Graph visualization has been applied in a wide range of domains to model and support the analysis of different relationships between elements, from protein-protein interaction [1] and biomolecular relationships [2] to social networks [3]. Despite its popularity, effective graph visualization presents several challenges, especially when dealing with dense graphs with many vertices or edges [4, 5]. In these scenarios, the visualizations usually present considerable overlapping of visual elements, resulting in cluttered layouts that make it hard or even impossible for users to extract relevant information. Clutter reduction is a frequent subject in data visualization [6]. In general, it aims to reorganize or transform visual elements so that the attained representation can reveal meaningful patterns hidden in the original layout. Specifically for graph visualization techniques, _Edge Bundling_ has obtained relative success in reducing visual clutter on node-link diagrams by bending and aggregating groups of edges [7, 8, 9]. Additionally, the curves' smoothness also improves the visual representations making it easier to follow high-level edge patterns [10], allowing to produce layouts that support the overview of large graphs. Over recent years, different edge bundling strategies have been proposed. The seminal technique, Hierarchical Edge Bundling (HEB) [11], employs an external hierarchical structure to guide the edges' bending and, therefore, cannot be used if such a structure is not provided. Several approaches have been devised to address this limitation, avoiding the need for any other information besides graph adjacency and vertex positions. Some examples include strategies based on force-directed placement [10; 12], geometry processing [13; 14], clustering [15; 16] and image processing [17; 18; 19]. Despite the high degree of clutter reduction these techniques can attain, they only use the visual space (graph embedding) to perform the edge bundling. So that resulting in aggregations that might not explicitly reflect the underlying data (edges or vertices attributes). Recently, the use of data information to guide the bundling gained attention [20; 21; 22; 23], usually adapting existing techniques. However, only edge information is considered, ignoring information on the vertices, narrowing their applicability. In this paper, we present _Similarity-Based Edge Bundling (SBED)_, an adaptation of the HEB technique to construct bundling layouts that do not depend on an external hierarchy and consider similarity relationships among the vertices to add semantics to the bundled representations. Our approach uses a two-step process. On the first step, we derive a distance-preserving _backbone_ structure to serve as a guide for the bundling, and, on the second, the straight edges are curved towards such a structure. Besides consistently representing the underlying data similarity relationships, a bonus of using this _backbone_ is the possibility of multiscale visualization and exploration. Bundled layouts can be explored into different levels of detail, from coarser levels, better suited for exploring the main patterns between groups, to finer levels, supporting the exploration of intra-group relationships. In summary, the main contributions of this paper are:  
* An approach to creating graph bundling layouts in which the bundles are defined based on similarity relationships;
* A strategy to explore bundling layouts using a multiscale approach using aggregation and adaptative bundling parameters; and
* A stable strategy to bundle edges in graphs with time-varying topology. In Section 2, we overview the more important graph edge bundling techniques, discussing their limitations. In Section 3, we explain the different strategies we develop to address the problem of creating bundled layouts that reflects the underlying data similarity, including the simplification procedure to allow multilevel navigation.