Dynamic multilevel graph layout and visualisation

This thesis addresses the issue of efficient dynamic graph drawing for large scale connected graphs with around 10,000 vertices. It contains three main contributions. Firstly, an efficient method for approximating the n-body calculations used in Force Directed Placement (FDP) is described, exploiting use of a multilevel scheme to approximate distance between groups of vertices much like the Barnes Hut Octree. The method suggests better representation of the graphs underlying relationships. In experiments this algorithm, referred to as Multilevel Global Force (MGF), reduces running time by an average of 40% compared to the popular Barnes Hut Octree approximation method. Secondly, optimisation methods used in static graph drawing (such as multilevel and approximation schemes) are adapted for use in dynamic graph drawing, simultaneously improving the quality of layouts produced and reducing the complexity such that large graphs with thousands of vertices can be drawn in interactive time. Thirdly, several techniques are introduced for incorporating graph changes into the dynamic graph drawing to differing extents, allowing the viewer to decide whether the ongoing layout should preserve the original layout or prioritise the graph changes. The works are combined to form an efficient multilevel dynamic graph drawing algorithm.

Name dc:type.qualificationname

phd

Level dc:type.qualificationlevel

doctoral

Grantor dc:publisher.institution

University of Greenwich

Year dc:date.issued

2016

Author dc:creator

• Crawford, Carl Jonathan

Advisors dc:contributor.advisor

• Walshaw, Christopher
• Soper, Alan

• QA Mathematics

Language dc:language

en