Yifan Hu
We propose a graph drawing algorithm that is both efficient and high quality. This algorithm combines a multilevel approach, which effectively overcomes local minimums, with the Barnes and Hut [1] octree technique, which approximates short- and long-range force efficiently. Our numerical results show that the algorithm is comparable in speed to Walshaw's [2] highly efficient multilevel graph drawing algorithm, yet gives better results on some of the difficult problems. In addition, an adaptive cooling scheme for the force-directed algorithms and a general repulsive force model are proposed.
The proposed graph drawing algorithm and others are included with Mathematica 5.1 and later versions in the package DiscreteMath`GraphPlot.
Notebook
PDF
HTML
1. Introduction
2. Definitions and Notations
3. Force-Directed Algorithms
4. Barnes-Hut Force Calculation
5. The Multilevel Algorithm
6. Numerical Results
7. Conclusions and Future Work
Acknowledgments
References
| |
Yifan Hu
Senior Developer
Wolfram Research, Inc.
100 Trade Center Drive
Champaign, IL 61820, USA
yifanhu@wolfram.com
|