A fast multi-scale method for drawing large graphs
David Harel, Yehuda Koren · Working Conference on Advanced Visual Interfaces (AVI) · 2000
We present a multi-scale layout algorithm for the aesthetic drawing of undirected graphs with straight-line edges. The algorithm is extremely fast, and is capable of drawing graphs of substantially larger size than any other algorithm we are awars of. For example, the algorithm achieves optimal drawings of 1000 vertex graphs in less than 3 seconds. The paper contains graphs with over 6000 nodes. The proposed algorithm embodies a new multi-scale scheme for drawing graphs, which can significantly improve the speed of essentially any force-directed method.
Cited by 130 works. doi:10.1145/345513.345353 Open-access PDF
Authors
References
- Graph drawing by force‐directed placement
- A hierarchical O(N log N) force-calculation algorithm
- Approximation Algorithms for NP-Hard Problems
- An algorithm for drawing general undirected graphs
- Graph Drawing: Algorithms for the Visualization of Graphs
- A Heuristic for Graph Drawing
- Clustering to minimize the maximum intercluster distance
- Drawing graphs nicely using simulated annealing
- A unified approach to approximation algorithms for bottleneck problems
- A fast adaptive layout algorithm for undirected graphs