A Potential-Field-Based Multilevel Algorithm for Drawing Large Graphs

Hachul, Dr. Stefan (2002) A Potential-Field-Based Multilevel Algorithm for Drawing Large Graphs. PhD thesis, Universitaet zu Koeln.

[img] Postscript - Requires a viewer, such as GSview
84Mb
[img] PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
12Mb

Abstract

The aim of automatic graph drawing is to compute a well-readable layout of a given graph G=(V,E). One very popular class of algorithms for drawing general graphs are force-directed 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 force-directed methods can visualize large graphs containing many thousands of vertices in reasonable time. However, only some of these methods guarantee a sub-quadratic running time in special cases or under certain assumptions, but not in general. The others are not sub-quadratic at all. We develop a new force-directed 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 worst-case running time of the new method is O(|V| log|V|+|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.

Item Type:Thesis (PhD)
Keywords:large graphs, force-directed methods, fast algorithms, multilevel algorithm, potential field, multipole method, general graphs
Classifications:M Methods > M.400 Force-directed / Energy-based
ID Code:539
Alternative Locations:http://kups.ub.uni-koeln.de/volltexte/2005/1409

Repository Staff Only: item control page