# 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
In Figure 2, the sub-tree 2 represents the resulting drawing swapping \(v^{\prime}.left\) with \(v^{\prime}.right\), putting \(v^{\prime}.left\) closer to \(v^{\prime}.parent.parent.right\) in case \(\delta(v^{\prime}.left,v^{\prime}.parent.parent.right)<\delta(v^{\prime}.right,v^{\prime}.parent.parent.right)\). Since only swaps between siblings are allowed, this adaptation can lead to a better overall distance preservation without corrupting the tree topology. Notice that this swapping strategy performs only local modifications, so it is not guaranteed that it produces the H-tree arrangement that best preserves the distance relationships on the plane. However, a global rearrangement is impracticable to be solved for large datasets. Nevertheless, due to the triangle inequality axiom of distance metrics, we expect to improve (when possible) the results of any given tree. The complete process is detailed on Algorithm 2. In this algorithm, initially the root is set to the origin of the visual space. Then, the root's children are linked to it using horizontal (or vertical) segments placing them equidistantly from the root's position. This process is recursively applied taking the children as roots of subtrees and alternating the segment directions perpendicularly,reducing the distance to the (sub) roots every recursion to avoid overlaps. In this process, every time the children of a (sub) root are placed, a test is performed to check if swapping their position improves distance preservation. In the algorithm, the function \(\textsc{SwapSiblings}(v^{\prime}.left,v^{\prime}.right)\) is used to swaps sibling vertices \(v^{\prime}.left\) and \(v^{\prime}.right\) in this process. ```
functionSwappingHTree(\(T\))  SwappingHTreeRec(\(T.root\), \(initial\_radius\), \(false\)) return\(T\) endfunctionfunctionSwappingHTreeRec(\(v^{\prime}\), \(radius\), \(hor\)) if\(v^{\prime}==T.root\)then\(v^{\prime}.x\gets 0\)\(v^{\prime}.y\gets 0\) else ifhorizontal\(==\)truethen\(\triangleright\) If it is an horizontal placement if\(v^{\prime}\) is left childthen\(v^{\prime}.x\gets v^{\prime}.parent.x-radius\) else\(v^{\prime}.x\gets v^{\prime}.parent.x+radius\) endif\(v^{\prime}.y\gets v^{\prime}.parent.y\) else\(\triangleright\) If it is an vertical placement if\(v^{\prime}\) is left childthen\(v^{\prime}.y\gets v^{\prime}.parent.y+radius\) else\(v^{\prime}.y\gets v^{\prime}.parent.y-radius\) endif endifSwap(\(v^{\prime}\))  Swap(\(v^{\prime}\))  SwappingHTreeRec(\(v^{\prime}.left,(radius/\sqrt{2})\)\(\
eg hor\)) SwappingHTreeRec(\(v^{\prime}.right,(radius/\sqrt{2})\), \(\
eg hor\)) endif endfunctionfunctionSwap(\(v^{\prime}\)) if\(v^{\prime}.parent==v^{\prime}.parent.left\)then\(\triangleright\) If the parent of \(v^{\prime}\) is a left child if\(\delta(v^{\prime}.left,v^{\prime}.parent.parent.right)<\delta(v^{\prime}.right,v^{\prime}.parent.parent.right)\)then\(\textsc{SwapSiblings}(v^{\prime}.right,v^{\prime}.left)\) endif else\(\triangleright\) If the parent of \(v^{\prime}\) is a right child if\(\delta(v^{\prime}.left,v^{\prime}.parent.parent.left)<\delta(v^{\prime}.right,v^{\prime}.parent.parent.left)\)then\(\textsc{SwapSiblings}(v^{\prime}.right,v^{\prime}.left)\) endif endfunction
```  
**Algorithm 2**Swapping H-tree algorithm. Figure 2: H-tree with swaps. The children \(v^{\prime}.left\) or \(v^{\prime}.right\) of a node \(v^{\prime}\) in the left sub-tree can be swapped to put closer to the sibling of its parent vertex \(v^{\prime}.parent.parent.right\) the most similar child to it. This operation potentially result in a layout with better local distance preservation (the right sub-tree) without changing the tree topology. As mentioned before, different from the radial layout, the H-tree layout focuses on the vertices instead of on the edges. Therefore, the distances between the data objects can be better preserved.