# Faster Force-Directed Graph Drawing
## 3 Experimental Comparison
### Results of Comparison  
To test Hypothesis (H1), we compared the quality of the drawings produced by FRLayout and FR+WSPD for the data sets (DS1), (DS2), (DS5) and (DS6) using a statistical test. More precisely, we want to show that the number of crossings produced by our FR+WSPD algorithm is at most 10% worse, and the standard deviation of the edge lengths is at most 25% worse than the original FRLayout algorithm. To see this, we formulate the following null hypothesis: the number of crossings (resp., the standard deviation of the edge lengths) yielded by FR+WSPD is more than 1.1-times (resp., 1.25) the value yielded by FRLayout. It turned out that we can reject this null hypothesis using a [PERSON] signed rank test [26] with high significance (\(p\)-values of 0.01 at most). Additionally, we compared the quality of the drawings produced by our FR+WSPD algorithm to that of other graph drawing algorithms. In order to vary as few parameters as possible, we kept the size of the graphs constant in this part of the study. We used all Rome graphs with exactly 100 vertices. The 140 graphs have, on average, 135 edges. The lower scatterplot in Figure 4 compares FR+WSPD to the above-mentioned four OGDF algorithms. In terms of the uniformity of edge lengths, there are three clear clusters: FM3 is  
Figure 4: Standard deviation of the edge lengths (\(y\)-axis) over the number of edge crossings (\(x\)-axis) for various variants of the algorithm, applied to all 140 Rome graphs with exactly 100 vertices, a subset of (DS1). **(Top)** Quality of the unmodified FRLayout algorithm and its variants FR+WSPD, FR+Quad and FR+Grid; **(Bottom)** FR+WSPD and some algorithms implemented in OGDF. For each algorithm, a vertical and a horizontal line mark its median performance. better and FastMultipole is worse than the rest (FRExact, GEM and FR+WSPD). In terms of crossings, however, FastMultipole is best, followed by GEM, FRExact, FM\({}^{3}\) and FR+WSPD. For the relatively dense graphs with 1000 vertices in Rand-1000 Vtc-HiDens (DS5), Figure 5 shows a similar picture, except that here, FR+Grid is clearly the worst in both measures. FR+WSPD is in the mid-field according to both measures. The upper scatterplot in Figure 4 compares the four variants of FR based on different speed-up techniques, which we have implemented in Java. In terms of the uniformity of edge lengths, FRLayout and FR+Quad are slightly better than FR+WSPD and FR+Grid. FR+Grid produces considerably more edge crossings than the other three variants. While FRLayout is somewhat better than FR+WSPD in both measures, there is support for Hypothesis (H1). To test Hypothesis (H2), we measured the runtimes of all algorithms on our test data sets. Whenever an input graph was not connected, we measured the runtime for drawing all of its connected components. In Java, we only measure the time used for the thread running the force-directed algorithm in our Java Virtual Machine (using the method java.lang.management.ManagementFactory.getThreadMXBean().getCurrentThreadCpuTime()); this eliminates the influence of the garbage collector and the JIT compiler on our measurements. In C++, we used the OGDF method ogdf::usedTime for measuring the CPU time. For each graph size, we display the mean runtime over all graphs of that size. Figure 6 shows the runtimes for a test set with smaller graphs: Rome (DS1). The runtime curves for the North graphs were very similar to those of the Rome graphs, but due to the much smaller number of graphs, less smooth. Due to the similarity, we only show the plots for the Rome graphs. Figure 7 shows the runtimes for the test sets with larger graphs; (DS3), (DS4) and (DS5). The results are as follows. As expected, FR+WSPD is much faster than FRLayout on larger graphs. We were surprised, however, to see that FR+WSPD starts overtaking FRLayout already around \(n\approx 100\).