Universität zu Köln

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

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

[img]
Preview
PDF
Download (12Mb) | Preview

    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 abstract:
    AbstractLanguage
    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:
    CreatorsEmail
    Hachul, Stefanhachul@informatik.uni-koeln.de
    URN: urn:nbn:de:hbz:38-14097
    Subjects: Data processing Computer science
    Uncontrolled Keywords:
    KeywordsLanguage
    Graphenzeichnen, kräftebasierte Algorithmen, große Graphen, N-Körper Simulationen, MultipolmethodenGerman
    graph drawing, force-directed algorithms, large graphs, N-body simulations, multipole methodsEnglish
    Faculty: Mathematisch-Naturwissenschaftliche Fakultät
    Divisions: Mathematisch-Naturwissenschaftliche Fakultät > Institut für Informatik
    Language: English
    Date: 2005
    Date Type: Completion
    Date of oral exam: 31 January 2005
    Full Text Status: Public
    Date Deposited: 04 Apr 2005 12:43:54
    Referee
    NameAcademic Title
    Jünger, MichaelProf. Dr.
    URI: http://kups.ub.uni-koeln.de/id/eprint/1409

    Actions (login required)

    View Item