Efficient, High-Quality Force-Directed Graph Drawing

Yifan Hu

6. Numerical Results

In this section we demonstrate the drawings using our algorithms on some large examples and also compare our algorithms with those of Walshaw [2], both in terms of efficiency and quality of layout.

The algorithms are implemented in Mathematica 5.1, under the GraphPlot package. To load the package, evaluate

This package has many graph theory functions. Among them, GraphPlot and GraphPlot3D draw graphs in 2D and 3D, respectively. Details of the package can be found in the Mathematica Help Browser.

The details for the algorithms we will demonstrate and the names they are denoted by follow. We also give the Mathematica command corresponding to each of the algorithms, where we use gr to represent the graph.

MSE() (Multilevel Spring-Electrical Model)

The Mathematica command for MSE() () is

MSE() (Multilevel Spring-Electrical Model with General Repulsive Force)

Multilevel Algorithm 2 with HYBRID coarsening scheme, octree data structure, and repulsive/attractive force given by (1). The cutoff radius for the repulsive force calculation is (11), with by default. The difference from MSE() is that the general repulsive force model (4) is used with parameter . MSE() is the same as MSE(). The Mathematica command for MSE() is

The Mathematica command for MSE() () is

MS() (Multilevel Spring Model)

Multilevel Algorithm 2 with HYBRID coarsening scheme, octree data structure, and repulsive/attractive force given by (5). The cutoff radius for the distance and force calculation is (12), with by default. The Mathematica command for MS() is

The Mathematica command for MS() () is

SE (Spring-Electrical Model)

Algorithm 1 with octree data structure and repulsive/attractive force given by (1). The Mathematica command for SE is

MLFDP

The multilevel force-directed placement algorithm (MLFDP) from [2].

For all the preceding algorithms, we used a tolerance of to be comparable with Walshaw [2]. All our results are from a 3.0 GHz Pentium 4 machine with 2 GB of memory and a 512 KB cache under a Linux operating system. Our code is written in C and compiled with gcc using compilation flag "gcc -O2".

6.1. Comparison with Walshaw

In this section we compare our algorithm with that of Walshaw [2].

Table 1 lists a set of nine test problems from [2]. Some of these problems originate from engineering applications for which there is a known layout. Table 2 gives the CPU time for MSE(2) and MSE(), as well as the CPU time for the multilevel force-directed placement algorithm (MLFDP) from [2]. To see the extra cost of the multilevel approach, we also include the CPU time for the single level spring-electrical model, SE, in the last column of the table. The set of nine problems were chosen to be the same as those in Table 3 of [2]. We draw all the graphs in 2D and use these layouts for all the subsequent figures. However to be able to compare them with [2], we also laid out the last four graphs in 3D, even though sierpinski10 is really a 2D graph and, as Figure 12 shows, we can layout in 2D just fine.

Notice that Walshaw's CPU results were for a 1 GHz machine, 1/3 of the clock speed of our machine. However, based on our experience of clock speed and actual performance, we would expect the performance of our machine to be less than three times of Walshaw's.

Walshaw's MLFDP algorithm should be somewhat similar to our MSE(2), because both employ a similar cutoff radius. There are, however, some differences. MSE(2) uses the octree data structure and searches through the structure to decide if a cluster of vertices can form a supernode or should be excluded because it is outside the cutoff radius. So we have two approximations. In terms of CPU time, forming supernodes reduces the number of repulsive force calculations, but searching through the octree data structure is more expensive than the regular mesh-like data structures used by Walshaw to implement the cutoff radius. Therefore, overall, we expect the complexity of MLFDP and MSE(2) to be comparable. This is confirmed in Table 2. MLFDP and MSE(2) indeed do have quite comparable CPU time in general, although MSE(2) is notably faster on finan512, while MLFDP is notably faster on dime20. MSE(), which does not ignore long-range force, is only on average 21% more expensive than MSE(2).

Comparing multilevel algorithm MSE() with its single level counterpart SE, it is seen that MSE() is no more than twice as expensive, in fact for most graphs the difference is small. It is surprising that for sierpinski10, SE is more expensive than MSE() for both the 2D and 3D layouts! A careful examination of the innermost loops of the force calculations and octree code reveals that MSE() takes between two to three times as many operations as SE. The abnormality in CPU time is due to poor cache performance of the octree code in SE. SE starts from a random layout and never quite gets to a good layout for large graphs. When looping over vertices in the natural order to find their supernodes in the octree code, the locations of the vertices are unpredictable. The multilevel algorithm MSE(), on the other hand, always starts from a good initial layout. For most of the graphs in Table 1, the natural vertex ordering is such that if two vertices are close in their indices, they also tend to be close in their physical locations in the original layout. Thus in the octree code, roughly the same squares tend to be examined again and again when finding supernodes for consecutive vertices. This means that cache performance is very good for multilevel algorithm MSE(), but very poor for single level algorithm SE. This analysis is confirmed when we randomly shuffle the vertices. With such a random ordering, CPU timings for SE stay roughly the same, while the CPU timings for MSE() increase about twice.

The preceding analysis may suggest that the multilevel algorithm is susceptible to poor initial vertex indexing. However, this is not true. First, large graphs tend to have good natural ordering. Second, poor ordering can be easily remedied by preordering the vertices using a suitable ordering algorithm that is inexpensive. For example, we used the METIS [10] nested dissection algorithm to order previously randomly shuffled graphs, using the adjacency matrix of the graphs, and then applied the multilevel algorithm to the resulting graphs. We found that the CPU timings of MSE() on these preordered graphs are very comparable to those in Table 2. In fact for dime20, the CPU time is reduced from 290.6 to 252.3 with nested dissection preordering! Nested dissection preordering, however, has no effect on the cache performance of SE, due to its poor initial and subsequent layouts. It is possible to improve SE by ordering the vertices using a nested dissection based on the physical locations of the vertices, but since SE is not a good graph drawing algorithm anyway, we will not pursue this further here.

Graph |V| |E| Avg. Degree Diameter Graph Type
c-fat500-10 500 46627 186.5 4 Random clique test
4970 4970 7400 3. 106 2D dual
4elt 15606 45878 5.9 102 2D nodal
finan512 74752 261120 7. 87 Linear programming
dime20 224843 336024 3. 1179 2D nodal
data 2851 15093 10.6 79 3D nodal
add32 4960 9462 3.8 28 32-bit adder
sierpinski10 88575 177147 4. 1024 2D fractal
mesh100 103081 200976 3.9 203 3D dual

Table 1. Description of test problems.

Size CPU
Graph |V| |E| MLFDP* MSE(2) MSE() MS(4) SE
2D
c-fat500-10 500 46627 5.6 0.37 0.37 0.82 0.2
4970 4970 7400 6.4 2.5 2.7 10.9 1.8
4elt 15606 45878 24.3 9.4 11.7 102.9 9.2
finan512 74752 261120 363.8 56.6 59.8 3714.9 60.
dime20 224843 336024 264.3 195.5 290.6 1984.6 277.7
data 2851 15093 - 1.1 1.2 17.8 1.3
add32 4960 9462 - 3.1 3.3 44.4 2.6
sierpinski10 88575 177147 - 44.1 65.1 146.8 75.6
mesh100 103081 200976 - 91.6 109.4 5807.8 89.5
3D
data 2851 15093 6.6 2.3 2.4 33. 1.6
add32 4960 9462 12.5 6.2 7.1 230.7 3.2
sierpinski10 88575 177147 136.7 64.7 100.9 317.2 114.9
mesh100 103081 200976 431.1 158. 204. 6431.3 138.2

Table 2. CPU time (in seconds) for some force-directed algorithms. *: MLFDP data from [2], was for a 1 GHz Pentium III. All other times are for a 3 GHz Pentium 4. -: data not available.

As we would expect, MS(4) is very slow. This is because the spring model seeks to lay out vertices to have a physical distance equal to the graph distance. It is not obvious how to extend the octree methodology to the spring model. We can certainly work out the average graph distance of a cluster of vertices to another vertex, but to do so we still have to find the individual graph distances first. Therefore, no saving is achieved. A cutoff radius does allow us to reduce the complexity. However, we found that for good drawing quality, we have to use a relatively large radius. This is probably because, unlike the spring-electrical model, the spring model does not have a strong repulsive force and with the cutoff radius the repulsive force is weakened further. At a cutoff radius of 4, a large number of vertices are included, making the algorithm quite costly.

In terms of drawing quality, MSE(2) performs comparably to MLFDP, with MSE() the best. Both MSE(2) and MLFDP ignore long-range forces. However, the multilevel process enables them to inherit global information from coarser graphs, thus in most cases both still give good quality drawings. Nevertheless, for some problems, the adverse effect can be seen.

6.2. Comparison of Drawings

In the following, we give drawings of the graphs in Table 1. Our drawings of c-fat500-10 are the same as in [2] and are thus not included here. All our drawings are done in 2D, as we found that 2D drawings give us good representation.

Figure 7 (left) gives drawings of 4970 using MSE(). In this case the mesh around three corners is cluttered compared with the drawing in [2]. We believe this is due to the peripheral effect discussed in Section 3.1, which is reduced when there is a cutoff radius, as in Figure 10(b) of [2], and in MSE(2) (middle). An alternative way to reduce the peripheral effect is to explicitly use a weaker repulsive force model (3), as the drawing by MSE() (right) shows.

Figure 7. Drawings of 4970 by MSE() (left), MSE(2) (middle), and weaker repulsive force model MSE() (right).

Figure 8 (left) gives the drawing of finan512 using MSE(). This drawing is more appealing than Figure 13 of [2]. In that drawing, the circle is elongated, with the "knobs" flat and close to the circle. We believe this is due to the effect of ignoring the long-range repulsive force, so that the circle does not have enough force to make it rigid and rounded, and the knobs do not have enough force to push them out. We observed a similar side effect when we looked at the drawing given by MSE(2) in Figure 8 (right), where the circle is twisted, although it does draw the knobs well.

Figure 8. Drawings of finan512 by MSE() (left) and MSE(2) (right).

Figure 9 shows the drawings of dime20. The drawings are somewhat different from Figure 14(b) of [2]. In that drawing, the tip we see in Figure 9 at the top of the larger hole protrudes through the outer rim. Also, in [2], this large hole was replaced by a figure eight. Comparing the drawings of MSE() and MSE(2), the drawing by MSE(2) has thicker outer rims, because of the weakened repulsive force, and thus reduced peripheral effect.

Figure 9. Drawings of dime20 by MSE() (left) and MSE(2) (right).

Figure 10 gives the drawings of add32. The drawings are different from Figure 16(a) in [2] in that they occupy a larger area. Comparing the drawings of MSE() and MSE(2), the latter is "fluffier" in that the branches extend to occupy more space. This is another example of the peripheral effect of a strong repulsive force in MSE(). We found that for tree-type applications, drawings by MSE() tend to have leaves and some branches clinging to the main branches. MSE(2) suffers less because of the weakened repulsive force due to the cutoff radius. For these type of applications, it is often better to apply the general repulsive force model (3) with a weaker force given by . Figure 11 shows drawings with (MSE()) and (MSE()). In our view they give more details.

Figure 10. Drawings of add32 by MSE() (left) and MSE(2) (right).

Figure 11. Drawings of add32 with a weaker repulsive force by MSE() (left) and MSE() (right).

Figure 12 gives the drawings of sierpinski10. In [2] Walshaw uses a 3D layout since he found 2D layout unsatisfactory. We found our 2D layout to be good, particularly MSE(2). MSE() demonstrates again the peripheral effect. The strong repulsive force pushes some of the vertices out. The bottom of Figure 12 shows the result of using a general repulsive force model (3) with weaker force given by , which does not suffer from the peripheral effect.

Figure 12. Drawings of sierpinski10 by MSE() (left), MSE(2) (middle), and MSE() (right).

Figure 13 gives drawings of mesh100. Compared with the drawing in Figure 18(b) of [2], our drawings bear a closer resemblance to the actual mesh given in Figure 18(a) of [2].

Figure 13. Drawings of mesh100 by MSE() (left) and MSE(2) (right).

Overall, our algorithms give comparable drawings to those in [2]. For difficult graphs, notably finan512 and sierpinski10, we achieve more appealing drawings. The general repulsive force model (3) offers choices to overcome the peripheral effect and can sometimes give more appealing drawings. As a further example, Figure 14 shows a good alternative drawing of finan512, by using a slightly weaker repulsive force. A comparison with Figure 8 (left), shows that without a very strong repulsive force to push them outward, some of the "spikes" now point inward. We found that further weakening of the repulsive force would cause the circle not to be rounded, much like what happens in Figure 8 (right).

Figure 14. An alternative drawing of finan512 by MSE().

6.3. Comparing the Spring-Electrical Model with the Spring Model

In addition to efficiency considerations that favor the spring-electrical model, we also found that compared with the spring model, it gives good drawings for most graphs. The spring model, on the other hand, works particularly well for graphs originated from uniform or near-uniform meshes, albeit requiring more CPU time. The spring model works well for such graphs because it is possible to lay them out so that the physical distance is very close to the graph distance of vertices.

For example, Figure 4 (right) gives a drawing of jagmesh1 using MSE(). It is seen that closer to the outer boundary, the peripheral effect of the spring-electrical model is obvious. This effect can be reduced using a weakened repulsive force, as Figure 15 (left) shows using MSE(). However, the spring model, MS(4), gives probably the most appealing drawing, as shown in Figure 15 (right). The same happens to sierpinski10 (Figure 16) and mesh100 (Figure 17). Both come very close to what the graphs look like in their original layout, in Figure 17(a) and Figure 18(a) of [2]. MS(4) also draws the data graph quite well, compared with MSE(), as shown in Figure 18.

Figure 15. Alternative drawings of jagmesh1 of Figure 4 by MSE() (left) and MS(4) (right).

Figure 16. A drawing of sierpinski10 using MS(4).

Figure 17. A drawing of mesh100 using MS(4).

Figure 18. Drawings of data using MS(4) (left) and MSE() (right).

However, for graphs that come from a locally refined mesh, the spring model works poorly. For example, Figure 19 shows the drawing of 4elt by MS(4) (right) and MSE(). It is clear that MS(4) strives to draw the graph as uniformly as possible, but since this is not possible for such a highly refined graph, and in the absence of a strong long-range repulsive force, a lot of foldings occur near the highly refined regions. Therefore, overall we favor the multilevel SE algorithm for its efficiency and general good quality of drawings.

Figure 19. Drawings of 4elt by MSE() (left) and MS(4) (right).

6.4. Further Examples

In this section we demonstrate our algorithms with further examples from the University of Florida Sparse Matrix Collection (www.cise.ufl.edu/research/sparse/matrices). Three of the graphs (skirt, bodyy6 and pwt) have known layouts. Table 3 describes the graphs and the CPU time taken to lay these out in 2D.

Graph |V| |E| Diameter Graph Type CPU
skirt 12598 91961 98¹ NASA matrix 8.4
bodyy6 19366 57421 122 NASA matrix 14.4
pwt 36519 144794 262² NASA matrix 25.0
pkustk01 22044 478668 26 Beijing botanical exhibition hall 14.3
pkustk02 10800 399600 33 Feiyue twin tower building 9.5

Table 3. Problem description and CPU time (in seconds) for some graphs. : skirt has seven components; four of them are nontrivial and have diameters 98, 68, 68, and 39, respectively. : pwt has 57 components, 56 components are just a single vertex.

Figure 20 shows the original layout of the skirt graph. It is surprising to us that this mesh actually consists of seven components; three of these are just an isolated vertex. Of the four nontrivial components, one is the main tube and nozzle, another is the skirt/struts at the bottom of Figure 20 (right). The other two components are the two "rings" connecting the main tube/nozzle and the skirt. They are seen in Figure 20 (right) as one thick horizontal belt.

Figure 21 shows the drawings of the tube/nozzle and the skirt/struts. The tube/nozzle has a much finer mesh near the nozzle end, thus the drawing has the nozzle part expanded. The drawing of the skirt/struts is interesting. In the drawing, two struts protruding out of Figure 21 (left) are drawn separated from three pieces of the skirt, revealing the weak linkage between the struts and the pieces of skirts.

Figure 20. Original layout of skirt: two views.

Figure 21. Drawings of two components of skirt by MSE(): the skirt/struts (left); the tube/nozzle (right).

Figure 22 (left) shows the original layout of a highly refined mesh. The mesh is highly refined around the middle void and to its right. The drawing algorithm, in its effort to draw edges as uniformly as possible, turned the mesh inside out (Figure 22, right). The hole in the middle is actually the middle void in the original mesh. The original mesh is so highly refined to the right of the middle void that the drawing shows a folding. However, contrary to our intuition, using algorithms MSE() or MSE(), both having a weaker repulsive force, removes the folding (Figure 23). So it seems the folding is due to the strong repulsive force of the spring-electrical model, another example of the peripheral effect. The original mesh is nearly symmetric and all the drawings also exhibit good symmetry.

Figure 22. Original layout of bodyy6 (left) and drawing by MSE() (right).

Figure 23. Drawings of bodyy6 using MSE() (left) and MSE(2) (right).

Figure 24 (left) shows the pwt mesh, which is probably a mesh for a pressured wind tunnel. The drawing by MSE() corresponds to the original layout well. The large chamber in the original mesh has a mesh density similar to the pipe and is thus indistinguishable from the pipe in the drawing. In Figure 25 close-up views of the smaller chamber in the original layout and our corresponding drawing are given. The drawing depicts the details well.

Figure 24. Original layout of pwt (left) and a drawing by MSE() (right).

Figure 25. Close-up view of the original layout of pwt (left) and a drawing by MSE() (right).

Finally, Figure 26 shows drawings of pkustk01 and pkustk02. These two graphs have high average degrees (43 and 74, respectively). However, judging by the drawings, our algorithms performed very well.

Figure 26. Drawings of pkustk01 (left) and pkustk02 (right) using MSE().