# Similarity-Driven Edge Bundling: Data-Oriented Clutter Reduction in Graphs Layouts
## 3 Similarity-Driven Edge Bundling (SDEB)
### Backbone Construction  
The _backbone_ is a tree-like structure composed of intermediate vertices \(V^{\prime}=\{v^{\prime}_{1},v^{\prime}_{2},\ldots\}\) linking the data vertices \(V\) of \(G\). As discussed, its primary function is to serve as a guide to bend the edges to generate the bundles. In the _backbone_, every pair of data vertices \(v_{i},v_{j}\in V\) is linked through a sequence of vertices \(p_{ij}=\{v_{i},v^{\prime}_{1},v^{\prime}_{2},\ldots,v_{j}\}\) defining a path that pass through different intermediate vertices. Figure 1: SDEB overview. Using dissimilarities computed between graph vertices (data objects) as input, a _backbone_ to guide the bundling process is created linking the vertices according to their similarity. Next, the _backbone_ is mapped to the visual space using a tree layout strategy, and the graph is drawn bending the edges towards the _backbone_. When drawing the bundled graph, each edge \(e_{ij}\) that connects \(v_{i}\) and \(v_{j}\) is then curved towards the path \(p_{ij}\). In the _backbone_ various paths share intermediate vertices, so if i is carefully constructed, the bundling process results in groups of curved edges based on the data objects similarity. The _backbone_ is a crucial piece of our approach and must obey different design principles: **(1)** it should define paths between all pairs of data vertices, precisely connecting them according to their similarities, that is, paths between similar data vertices should contain less intermediate vertices than paths between dissimilar data vertices; **(2)** a unique path should connect any two data vertices, and; **(3)** a path between two data vertices should not pass through any other data vertex. The first and second principles are straightforward. Since the _backbone_ is used to attract edges for bundling, it must have paths connecting all pairs of data vertices as there could be edges between any pair of data vertices. Also, the path connecting two data vertices should be unique to avoid ambiguity problems during bending. The third principle is more involving. Suppose an edge \(e_{ij}\) connects the vertices \(v_{i}\) and \(v_{j}\), but that neither \(v_{i}\) nor \(v_{j}\) are connected to another vertex \(v_{k}\). Since the backbone is used to attract \(e_{ij}\) towards the path \(p_{ij}\), if \(v_{k}\subset p_{ij}\), the edge will be bent towards \(v_{k}\), giving the wrong impression that \(v_{i}\) and/or \(v_{j}\) are connected to \(v_{k}\), potentially resulting in misleading visual representations. Amongst the candidate techniques for constructing the _backbone_, the minimum spanning tree [31] built on top of a nearest-neighbor graph is discarded since it violates the principle **(3)**. We also discard hierarchical clustering techniques, such as the _Unweighted-pair Group Method with Arithmetic Means (UPGMA)_[32], since it is sensitive to certain distance distributions [33], and prone to produce unbalanced structures violating **(1)**. Although _Neighbor Joining (NJ)_[34] algorithm for phylogenetic tree construction obeys all the design principles, its applicability is limited to graphs with few nodes due to its high computational cost (\(O(n^{3})\)). Based on these considerations, we have developed _Similarity Tree (STree)_, an algorithm for the construction of the _backbone_ that addresses all the design principles while presenting a lower computational cost (\(O(n\log n)\)). STree is next described. Similarity Tree (STree)  
As already explained, the backbone is a tree-like structure where the intermediate vertices \(V^{\prime}\) are internal vertices, and the data vertices \(V\) are leaves. Also, to satisfy our primary goal of bundling according to the similarities amongst vertex groups, the length of the path between any two vertices \(v_{i},v_{j}\in V\) must be proportional to \(\delta(d_{i},d_{j})\).