1. Introduction

Graphs are often used to encapsulate the relationship between objects. Graph drawing enables visualization of these relationships. The usefulness of the representation is dependent on the aesthetics of the drawing. While there are no strict criteria for aesthetics, it is generally agreed that minimal edge crossing, evenly distributed vertices, and depiction of graph symmetry is desirable.

This problem has been studied extensively in the literature [3] and many approaches have been proposed. In this article we concentrate on drawing undirected graphs with straight-line edges using force-directed methods [4, 5, 6, 7]. Force-directed methods, however, are one of many classes of methods proposed for straight-edge drawing. Other methods include the spectral method [8] and the high-dimensional embedding method [9].

A force-directed algorithm models the graph drawing problem through a physical system of bodies with forces acting between them. The algorithm finds a good placement of the bodies by minimizing the energy of the system. There are many variations of force-directed algorithms. The algorithm of Fruchterman and Reigold [4], which is based on the work of [5, 6], models the graph drawing problem with a system of springs between neighboring vertices of the graph, pulling them together. At the same time, repulsive electrical forces that exist push all vertices away from each other. The algorithm of Kamada and Kawai [7], on the other hand, associates springs between all vertices, with the ideal length of a spring proportional to the graph distance of the vertices. In a force-directed algorithm, the energy of the system is typically minimized iteratively by moving the vertices along the direction of the force. This amount may be large initially, but reduces gradually based on a "cooling schedule."

There are two limiting factors in drawing large graphs for standard force-directed algorithms. The first is that the physical model typically has many local minimums, particularly so for a large graph. Starting from a random configuration, the system is likely to settle in a local minimum. This may be improved, to a limited extent, by using a slow cooling schedule at the expense of more iterations. Nevertheless, it is practically impossible to use the standard force-directed algorithms to find a good layout of very large graphs.

The second limiting factor is the computational complexity of the standard force-directed algorithms. In the algorithm of Fruchterman and Reigold [4], for any given vertex, repulsive force from all other vertices needs to be calculated. This makes the per iteration cost of the algorithm , with the number of vertices in the graph. The algorithm of Kamada and Kawai [7] requires the calculation of the graph distance among all vertices with the force based on that. Thus the algorithm not only has a computational complexity of , with the number of edges in the graph but also a memory complexity of , although the latter can be circumvented at the cost of repeated calculations of the graph distances on the fly, instead of storing them in memory.

To overcome the first limiting factor, a multilevel approach was proposed. This idea has been successfully used in many fields, including graph partitioning [10, 11, 12] and was found to be able to overcome the localized nature of the Kernighan-Lin algorithm. Fruchterman and Reigold [4, 1148] alluded to that type of solution when, in the context of overcoming local minimums, they stated "we suspect that if we apply a multi-grid technique that allows whole portions of the graph to be moved, it might be of some help...". Harel and Koren [13], extending the earlier work of Hadany and Harel [14], proposed the so-called multiscale approach. In that approach, a sequence of coarser and coarser graphs are formed by finding the -centers and the distance matrix associated with them. They used the Kamada and Kawai spring model [7], thus incurring high computational complexity for distance calculation and memory. Although, for the force calculation the algorithm has a computational complexity of , achieved by restricting force calculation to a neighborhood, thus ignoring long-range force. Gajer et al. [15] built up the multilevel of graphs by using maximal independent vertex sets, with the th level consisting of a maximal independent vertex set such that the vertices are of distance apart. They avoided the high computational and memory complexity by calculating the graph distances on the fly and only for a restricted neighborhood, thus also ignoring the long-range force. Walshaw [2] proposed a multilevel algorithm and demonstrated that it was able to draw graphs as large as a quarter of a million vertices in a few minutes. Based on the author's earlier work in graph partitioning, the coarser graphs are formed by finding a maximal independent edge set and collapsing these edges. The forces between vertices are based on the Fruchterman and Reigold spring-electrical model [4]. Long-range force is again ignored by restricting the force calculation to a neighborhood with a radius that decreases as one moves from coarser to finer graphs and coincides with the radius used in the original graph.

Reducing the computational cost by restricting force calculation to a neighborhood has been an often used practice, dating at least as far back as Fruchterman and Reigold [4]. Such a practice, however, comes at a cost. Because long-range forces are ignored, there is no force to evenly distribute faraway vertices. When used within the multilevel approach, Walshaw [2] argued that global untangling has been achieved on coarser graphs, thus for the final large graphs, restricting force calculation to a small neighborhood does not penalize the quality of the placement. While this is to a large extent true, for some graphs we found that the lack of long-range force did hurt at least one, if not more, of the drawings in [2].

It is possible to take account of long-range forces in an efficient way in the spring-electrical model. In this model the attractive force (the spring force) is only between neighboring vertices, while the repulsive force is global and is proportional to the inverse of the (physical) distance between vertices. The repulsive force calculation resembles the -body problem in physics, which has been well studied. One of the widely used techniques for calculating the repulsive forces in time with good accuracy, but without ignoring long-range force, is to treat groups of faraway vertices as a supernode using a suitable data structure, as in the Barnes and Hut algorithm [1]. This idea was implemented for graph drawing by both Tunkelang [16] and Quigley and Eades [17, 18]. Tunkelang combined the Barnes and Hut algorithm with a conjugate gradient method, thus per iteration computational is only , even though long-range forces are approximated to the required accuracy. However, the algorithm is not suitable for large graphs because the conjugate gradient is a local optimization algorithm and the number of conjugate gradient iterations increases as the size of the graph increases. Quigley and Eades [17, 18] also used the Barnes and Hut algorithm for efficient and accurate force calculation. In addition, they employed a multilevel scheme that they called hierarchical clustering. However, they used that scheme for the visual abstraction of graphs, rather than for the placement of vertices. Therefore, the algorithm was not suitable for large graphs.

In this article we propose an algorithm that is both efficient and of high quality for large graphs. The algorithm is included with Mathematica 5.1 and later versions in the package DiscreteMath`GraphPlot. We combine a multilevel approach, which effectively overcomes local minimums, with the Barnes and Hut octree algorithm, which approximates short- and long-range forces satisfactorily and efficiently. In addition, we propose an adaptive cooling scheme for the basic force-directed algorithms and a scheme for selecting the optimal depth of the octree/quadtree in the Barnes and Hut algorithm. Our numerical results show that the algorithm is competitive with Walshaw's [2] highly efficient graph drawing algorithm, yet gives better results on some of the difficult problems. We also analyze the distortion effect of the standard Fruchterman-Reigold spring-electrical model and propose a general repulsive force model to overcome this side effect.

In Section 2, we give definitions and notations. In Section 3, we present the basic force-directed algorithms, as well as an adaptive cooling scheme. In Section 4, we briefly introduce the Barnes-Hut force calculation algorithm. In Section 5, we describe the multilevel scheme used. In Section 6, we compare the efficiency and drawings of our algorithm with that of Walshaw [2]. In Section 7, we conclude by suggesting some future works.