Hachul, Stefan
(2002)
A PotentialFieldBased Multilevel Algorithm for Drawing Large Graphs.
PhD thesis, Universitaet zu Koeln.
Abstract
The aim of automatic graph drawing is to compute a wellreadable layout of a given graph G=(V,E). One very popular class of algorithms for drawing general graphs are forcedirected methods. These methods generate drawings of G in the plane so that each edge is represented by a straight line connecting its two adjacent nodes. The computation of the drawings is based on associating G with a physical model. Then, the algorithms iteratively try to find a placement of the nodes so that the total energy of the physical system is minimal. Several forcedirected methods can visualize large graphs containing many thousands of vertices in reasonable time. However, only some of these methods guarantee a subquadratic running time in special cases or under certain assumptions, but not in general. The others are not subquadratic at all. We develop a new forcedirected algorithm that is based on a combination of an efficient multilevel strategy and a method for approximating the repulsive forces in the system by rapidly evaluating potential fields. The worstcase running time of the new method is O(V logV+E) with linear memory requirements. In practice, the algorithm generates nice drawings of graphs containing up to 100000 nodes in less than five minutes. Furthermore, it clearly visualizes even the structures of those graphs that turned out to be challenging for other tested methods.
Actions (login required)

View Item 