# Faster Force-Directed Graph Drawing
## 3 Experimental Comparison
### Results of Comparison
For the Java variants, we could isolate the part of the running time that is used for the computation of the repulsive forces, which is the part we have improved and in which we are most interested; see Figure 6 and compare the top plot that shows the total running times to the bottom plot that shows the times needed for computing the repulsive forces. To show more details in the bottom plot, note that we used a different scale on the \(y\)-axis. The plot clearly shows that, as expected, computing the repulsive forces dominates the total running time. Figure 5: Standard deviation of the edge lengths (\(y\)-axis) over the number of edge crossings (\(x\)-axis) for various variants of the algorithm, applied to data set Rand-1000 Vtc-HiDens (DS5). It shows the quality of the unmodified FRLayout algorithm and its variants FR+WSPD, FR+Quad, and FR+Grid, together with some algorithms implemented in OGDF. For each algorithm, a vertical and a horizontal line mark its median performance. Note that the horizontal line for FRLayout is hidden behind that of FRQuad. On larger graphs, FR+WSPD turned out to be faster than all other algorithms in our comparison, except for FastMultipole for the very large, but low-density graphs in Rand-IncVtc-LoDens (DS3) and except for FR+Grid in the other two data sets (DS4) and (DS5). Recall, however, that FR+Grid tends to produce a much more edge crossings (Figure 5). Concerning the comparison between Java and C++, FRExact (in C++) is roughly 2-3-times faster than FRLayout (in Java) for graphs of constant density; see Figure 5 (top and bottom). Increasing the number of edges slows FRLayout down much more than FRExact; see Figure 5 (middle). Of course, the comparison between different programming languages is not really fair because every language has its own advantages and disadvantages regarding efficiency. Still, our experiments show that the running times of FR+WSPD are in the same order of magnitude as those of OGDE. The quality measures and runtimes for data set Hachul (DS6) are shown in Figure 8. We do not show absolute values for this data set, as the graphs are very different from each other and the differences in the results are hard to see in a properly-scaled plot. Instead, we rank the results from 1 (best)-8 (worst). The plots show that the quality depends on the instance: for many instances, FR+WSPD is quite good in terms of edge crossings, while it is often worse in terms of edge length deviation. In terms of running time, FR+WSPD is usually among the two or three fastest  
Figure 6: The runtimes for Rome (DS1) as a function of the number of vertices. The upper plot shows the total runtime, the lower plot only the time needed for computing the repulsive forces (which we could only measure for the Java implementations). Note that the \(y\)-axes use different scales. Each point in the plots represents the mean value of the runtimes on all graphs in the test set with the given number of vertices. The markers are used only as a tool to identify the plots. implementations in our comparison, regularly beaten only by FR+Grid (which produces many more edge crossings). Figures 9-11 show some example graphs drawn by six of the eight algorithms in our comparison. These artificial graphs were generated by [PERSON] and [PERSON] (2016). Figure 7: **(Top)** Data set Rand-IncVtc-LoDens (DS3); 40 random graphs with increasing number of vertices and average degree five; **(Middle)** Data set Rand-5000 Vtc-IncDens (DS4); 40 random graphs with 5000 vertices and average degree ranging from 2–41 (the graphs with less than 25,000 edges actually consist of slightly less than 5000 vertices, as we only consider the largest connected component of each graph); **(Bottom)** Data set Rand-1000 Vtc-HiDens (DS5); 40 random graphs generated with the same parameters (1000 vertices and about \(10,000\) edges). The \(x\)-axis displays the index of the instances. Each marker represents one instance. Figure 8: Comparison of the quality and runtimes of the results for data set Hachul (DS6).