# Similarity-Driven Edge Bundling: Data-Oriented Clutter Reduction in Graphs Layouts
## 3 Similarity-Driven Edge Bundling (SDEB)
### Graph Drawing
#### 3.2.1 Positioning the Vertices  
Although different algorithms and strategies for mapping a graph onto a plane exist, most of them are computationally expensive, especially those seeking to preserve distance relationships between vertices [4]. To address such a limitation, in our approach, instead of mapping the graph \(G\), we map the _backbone_. Since the _backbone_ is a binary tree, its mapping requires less computation. In this paper, we use two different strategies to make a better use of the available space, and to improve vertices' distance preservation: the _radial layout_ algorithm [36] and an adaptation of the _H-tree_ algorithm [37]. In the radial layout, the data vertices are distributed around a circle, and the _backbone_'s intermediate vertices are placed on the inner concentric circles, with its root in the center. In this paper, the distribution of data vertices \(V\) on the circle follows the order imposed by the _backbone_. The data vertices (leaves) are placed side-by-side following a canonical post-order traversal (visiting the left sub-tree, right sub-tree, and then processing the vertex). Hence, the vertices one-dimensional mapping on the circle preserves the distance relationships encoded by the _backbone_ up to an extent. An interesting feature of the radial layout, particularly useful for bundling, is that it focuses on edges instead of vertices' spatial positioning. Thereby, there is more visual space to present the graph connections and reduce the visual clutter. On the other hand, the H-tree layout is focused on vertices. In the original H-tree algorithm, the vertices are positioned through a recursive process linking nodes trough perpendicular line segments, resulting in a fractal structure with a repeating pattern that resembles the letter \"H\". In this process, the root vertex, \(v^{\prime}_{root}\) is initially placed in the center of the visual space \(R\). \(R\) is then vertically (or horizontally) split into two regions of equal areas, \(R.left\) and \(R.right\), to contain the root's sub-trees. The root's child nodes, \(v^{\prime}.left\) and \(v^{\prime}.right\), (if they exist) are placed in the center of these two regions respectively, and are linked to \(v^{\prime}_{root}\) through a horizontal (or vertical) line segment. The regions \(R.left\) and \(R.right\) are then horizontally (or vertically) split to contain the sub-trees of \(v^{\prime}.left\) and \(v^{\prime}.right\), respectively, and the children of \(v^{\prime}.left\) and \(v^{\prime}.right\) are linked through vertical (or horizontal) line segments to them. This process continues until all vertices are drawn. In the original H-tree algorithm, distance are not taken into consideration in the drawing process. So we modify it to preserve vertices' distances on the produced layouts by swapping sibling vertices. The idea is outlined on Figure 2. Considering that the vertex \(v^{\prime}\) (in red) on the sub-tree 1 has been processed, and coordinates on the plane have been assigned to it. Before processing its children sub-trees, \(v^{\prime}.left\) and \(v^{\prime}.right\), a test is performed to check if swapping them improves the distance preservation regarding the sibling of its parent \(v^{\prime}.parent.parent.right\) (in blue). Recall that \(v^{\prime}.left\) and \(v^{\prime}.right\) represent centroids of two (sub)clusters of data vertices, and that \(v^{\prime}.parent.parent.right\) represents a (super)cluster encompassing other similar (sub)clusters. Thereby, swapping \(v^{\prime}.left\) with \(v^{\prime}.right\) (in green) to place the most similar vertex, and therefore all its descendant vertices, closer to \(v^{\prime}.parent.parent.right\), and therefore all its descendant vertices, when drawing the tree potentially improves the distance preservation between the clusters represented by \(v^{\prime}.left\) and \(v^{\prime}.right\) with respect to \(v^{\prime}.parent.parent.right\). The same applying to any other vertex of the _backbone_.