7. Conclusions and Future Work

In this article we proposed an algorithm that uses a multilevel approach to find global optimal layouts and the octree technique to approximate short- and long-range forces satisfactorily and efficiently. These two techniques were each proposed earlier for graph drawing [2, 16, 18], but as far as we are aware, were never combined to form one powerful algorithm for large-scale graph drawing. A number of practical techniques, including adaptive step and octree depth control, and a hybrid coarsening scheme, were introduced for the algorithm to work effectively. This algorithm is demonstrated to be both efficient and of high quality for large graphs, competitive to Walshaw's [2] highly successful graph drawing algorithm, yet gives better drawings on some difficult problems.

We also proposed a general repulsive force model to overcome the peripheral effect of the spring-electrical model. Finally, we compared the spring-electrical model with the spring model and demonstrated examples where the spring model may be suitable.

Both the multilevel approach and the octree data structure do have limitations. For example, both the EC coarsening scheme and the MIVS-based coarsening scheme would not work effectively on star graphs (a graph with one vertex connected to all other vertices and no two other vertices connected). The former would coarsen too slowly thus having unacceptable complexity, while the latter would coarsen too fast and not preserve the graph information on the coarser graphs. The parameter in the Barnes and Hut octree algorithm is empirically fixed (to 1.2 in all our drawings). We experienced one case where this value gives an artifact only corrected with a smaller value It may be possible to correct this artifact without changing the value by adding a random offset to the first square of the octree. These limitations remain a topic for further investigations. However, in general the proposed algorithm performed extremely well on a range of graphs from different application areas, a small number of which were shown.

The graph drawing algorithm presented in this article is in the Mathematica 5.1 release (November 2004).

After the completion of this article, our attention was drawn to an independent work by Hachul and Jünger [28]. In that paper, the multilevel approach is combined with the multipole expansion technique [29] to give a algorithm. The efficiency and quality of the algorithm in that paper appear to be at the same level as this article, although many details differ, including the multilevel scheme and the force approximation.