Drawing Large Graphs with a Potential-Field-Based Multilevel Algorithm (Extended Abstract)

Hachul, Stefan and Jünger, Michael (2004) Drawing Large Graphs with a Potential-Field-Based Multilevel Algorithm (Extended Abstract). In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004 , pp. 285-295(Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_29).

Full text not available from this repository.

Abstract

Force-directed graph drawing algorithms are widely used for drawing general graphs. However, these methods do not guarantee a sub-quadratic running time in general. We present a new force-directed method that is based on a combination of an efficient multilevel scheme and a strategy for approximating the repulsive forces in the system by rapidly evaluating potential fields. Given a graph G=(V,E), the asymptotic worst case running time of this method is O(|V|\log|V|+|E|) with linear memory requirements. In practice, the algorithm generates nice drawings of graphs containing 100000 nodes in less than 5 minutes. Furthermore, it clearly visualizes even the structures of those graphs that turned out to be challenging for some other methods.

Item Type:	Conference Paper
Additional Information:	10.1007/978-3-540-31843-9_29
Classifications:	P Styles > P.720 Straight-line M Methods > M.400 Force-directed / Energy-based
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/595

Actions (login required)

View Item