# Faster Force-Directed Graph Drawing
## 3 Experimental Comparison
### Experimental Setup  
Apart from FRLayout and FR+WSPD, we implemented the quadtree-based speed-up method of [PERSON] [4], which we call FR+Quad, and a grid-based approach suggested already by [PERSON] and [PERSON] [2], which we call FR+Grid. To widen the scope of our study, we included some algorithms implemented in C++ in OGDF [19]: GEM (short for Graph Embedder) of [PERSON] et al. [12], FM\({}^{3}\) (short for Fast Multipole Multilevel Method) of [PERSON] and [PERSON] [6], the FastMultipoleMultilevelEmbedder of [PERSON] (which is based on the idea of FM\({}^{3}\) and [PERSON]'s thesis [14]; we will call this variant simply FastMultipole), and FRExact (the exact FR implementation in OGDF; the corresponding class is called SpringEmbedderFRExact). We combine FRExact and GEM with MultilevelLayout in OGDF for our experiments. The other algorithms already include a multilevel implementation. Additionally, we use the ComponentSplitterLayout, as some OGDF algorithms can handle only connected graphs. Our modified Java algorithms use the same termination criterion as FRExact. They are still, however, different in the implementation details (for example, the effect of the cooldown function), which leads to a different number of iterations when comparing the two implementations. Therefore, the relationships between the algorithms from JUNG and OGDF have to be interpreted with caution. In particular, the runtimes should not be compared in absolute numbers as the premises are very different for Java and C++. We tested our algorithms on six data sets:  
1. [label=(DS1)]
2. Rome: The Rome graph collection [23] contains 11,528 undirected connected graphs with 10-100 vertices each. 3. North: The North graphs [24], a subset of the AT&T graph collection, contain 1277 directed connected graphs with 10-100 vertices each. We only consider the underlying undirected graphs. 4. Rand-IncVtc-LoDens: A set of 40 random graphs that we generated using the class EppsteinPowerLawGenerator [25] in JUNG, which yields graphs whose structure is similar to web graphs. We generated instances with 2500, 5000,7500,..., 100,000 vertices and approximately 2.5-times as many edges. We considered only the largest connected component of each generated graph, which contains most of the original vertices. 5. Rand-5000 Vtc-IncDens: A set of 40 random graphs generated as (DS3). We fixed the number of vertices to 5000 and generated approximately \(1,1.5,2,\ldots,20,20.5\)-times as many edges to be able to test graphs with different densities. We considered only the largest connected component of each generated graph. This affected only the graphs with less than 25,000 edges. 6. Rand-1000 Vtc-HiDens: A set of 40 random graphs generated as (DS3). We fixed the number of vertices to 1000 and the number of edges to approximately 10,000. Each of these graphs is connected. 7. Hachul: The set of artificial graphs generated by [PERSON] and [PERSON] [22]. We use a subset of 45 graphs containing up to 10,000 vertices and up to 22,402 edges for our experiments. Some of these graphs are not connected. The experiments were performed on an Intel Xeon CPU with 2.67 GHz and 16 GB RAM running Linux. The computer has 16 cores, but we did not parallelize our code. During our experiments, only one core was operating at close-to-full capacity. We measured the quality of the drawings by (a) the number of edge crossings and (b) the standard deviation of the edge lengths (normalized by the mean edge length). These criteria have been used before to compare force-directed layout algorithms [11; 12]. We did not measure our quality criteria on the large graphs--(DS3) and (DS4)--as the running time to count the number of edge crossings was too high in our naive implementation. We first compared the outputs of FR+WSPD for different values (0.0001, 0.001, 0.01, 0.1, 1 and 10) of the separation constant \(s\) on (DS1).