Universität zu Köln

Hachul, Stefan (2005). A Potential-Field-Based Multilevel Algorithm for Drawing Large Graphs. PhD thesis, Universität zu Köln.

Preview

PDF diss_hachul.pdf Download (13MB)

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 thesis)
Translated title:	Title Language Ein potenzialfeldbasierter Multilevelalgorithmus zum Zeichnen großer Graphen German
Translated abstract:	Abstract Language Das Ziel beim Automatischen Zeichnen von Graphen besteht darin, zu einem gegebenen Graphen G = (V,E) eine Zeichnung zu berechnen, welche seine Struktur leicht verständlich visualisiert. Eine sehr verbreitete Klasse von Methoden zum automatischen Zeichnen von allgemeinen Graphen sind die so genannten kräftebasierten Verfahren. Diese Verfahren erzeugen Zeichnungen von G, bei denen Kanten durch Geraden repräsentiert werden. Dabei wird zunächst G mit einem physikalischen Modell identifiziert. Anschließend versuchen diese Algorithmen iterativ eine Platzierung der Knoten zu finden, so dass die Gesamtenergie des induzierten physikalischen Systems minimal ist. Einige kräftebasierte Verfahren können Graphen mit mehreren tausend Knoten in angemessener Zeit visualisieren. Allerdings garantieren nur manche dieser Verfahren in speziellen Fällen oder unter bestimmten Annahmen - jedoch nicht im Allgemeinen - eine subquadratische Laufzeit. Die anderen haben in keinem Fall ein subquadratisches Laufzeitverhalten. Wir entwickeln einen neuen kräftebasierten Algorithmus, der auf der Kombination einer effizienten Multilevelstrategie mit einer Methode zur approximativen Berechnung abstoßender Kräfte durch eine schnelle Auswertung von Potentialfeldern basiert. Die obere asymptotische Laufzeitschranke ist O(|V| log|V|+|E|) bei linearem Speicherplatzverbrauch. Praktische Experimente zeigen, dass die neue Methode Graphen mit bis zu 100000 Knoten in weniger als fünf Minuten übersichtlich darstellen kann. Zudem wird auch die Struktur solcher Graphen, die anderen getesteten Verfahren Probleme bereiten,leicht verständlich visualisiert. German
Creators:	Creators Email ORCID ORCID Put Code Hachul, Stefan hachul@informatik.uni-koeln.de UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-14097
Date:	2005
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Uncontrolled Keywords:	Keywords Language Graphenzeichnen, kräftebasierte Algorithmen, große Graphen, N-Körper Simulationen, Multipolmethoden German graph drawing, force-directed algorithms, large graphs, N-body simulations, multipole methods English
Date of oral exam:	31 January 2005
Referee:	Name Academic Title Jünger, Michael Prof. Dr.
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/1409