# Faster Force-Directed Graph Drawing
## 2 Algorithm
### The Force-Directed Algorithm  
The general principle of a force-directed algorithm is as follows. In every iteration, the algorithm computes forces on the vertices. These forces depend on the current position of the vertices in the drawing. The forces are applied as an offset to the position of each vertex. The algorithm terminates after a given number of iterations or when the forces get below a certain threshold.  
A classical force-directed algorithm, such as FR, computes, in every iteration, an attractive force for any pair of adjacent vertices and a repulsive force for any pair of vertices. We follow [PERSON] and [PERSON] [2] and use forces \(F_{\text{attractive}}(u,v)=d^{2}(u,v)/c\) and \(F_{\text{repulsive}}(u,v)=-c^{2}/d(u,v)\), where \(c\) is a constant describing the ideal edge length and \(d(u,v)\) is the distance between vertices \(u\) and \(v\) in the current drawing.  
Our modified algorithm is shown in Algorithm 1. We do not modify the computation of the attractive forces. We first compute a fair split tree \(T\) for the current positions of the vertices of \(G\) (which are stored in the leaves of \(T\)). Each node \(\mu\) of \(T\) corresponds to the set of vertices in the leaves of the subtree rooted at \(\mu\). We need to know the positions of the barycenters of the sets corresponding to the nodes of \(T\) to compute the values of the repulsive forces. Those can be computed in linear time by traversing the split tree bottom-up. We start with the leaves of the split tree, which only consist of one vertex. The barycenter of a one-element set is equal to the vertex position, of course. For the other nodes in the split tree, we can compute the barycenter as the weighted sum of the barycenters of its child nodes.  
```
//attractive forces for adjacent vertices: foreach\(e=u,v\in E\)do \(u.\text{addForce}(F_{\text{attractive}}(u,v))\); \(v.\text{addForce}(F_{\text{attractive}}(v,u))\); end //approximation of repulsive forces:  Compute a fair split tree \(T\) for the current positions of the vertices (stored in the leaves of \(T\)).;  For each node \(\mu\) of \(T\), compute the barycenter \(c(\mu)\) of the leaves of the subtree rooted in \(\mu\). ;  Compute a WSPD \((A_{i},B_{i})_{i=1,\ldots,k}\) from \(T\); each \(A_{i}\) (\(B_{i}\)) corresponds to a node \(\alpha_{i}\) (\(\beta_{i}\)) of \(T\).; for\(i=1\)to\(k\)do \(\alpha_{i}.\text{addForce}(|B_{i}|\cdot F_{\text{repulsive}}(c(\alpha_{i}),c( \beta_{i})))\); \(\beta_{i}.\text{addForce}(|A_{i}|\cdot F_{\text{repulsive}}(c(\beta_{i}),c( \alpha_{i})))\); end  Traverse the split tree top-down to compute the total force for every vertex of \(G\).
```  
**Algorithm 1**WSPD-Based Force Computation for a Graph \(G=(V,E)\).  
From \(T\), we compute a WSPD \((A_{i},B_{i})_{i}\) for the current vertex positions. Each set \(A_{i}\) (and \(B_{i}\)) of the WSPD corresponds to a node \(\alpha_{i}\) (and \(\beta_{i}\)) of \(T\). For each pair \((A_{i},B_{i})\) of the WSPD, we compute \(F_{\text{repulsive}}\) from the barycenter of \(A_{i}\) to the barycenter of \(B_{i}\) (and vice versa) and store the results (in an accumulative fashion) in \(\alpha_{i}\) and \(\beta_{i}\). Finally, we traverse \(T\) top-down. During the traversal, we add to the force of each node the force of the parent node. When we reach the leaves of \(T\), which correspond to the graph vertices, we have computed the resulting force for each vertex.