Crawford, Carl Jonathan (2016) Dynamic multilevel graph layout and visualisation. PhD thesis, University of Greenwich.

Preview

PDF Carl Jonathan Crawford 2016.pdf - Published Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (12MB) | Preview

Abstract

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.

Item Type:	Thesis (PhD)
Uncontrolled Keywords:	static graph drawing; dynamic graph drawing; algorithms; multilevel global force;
Subjects:	Q Science > QA Mathematics
Faculty / School / Research Centre / Research Group:	Faculty of Engineering & Science > School of Computing & Mathematical Sciences (CMS) Faculty of Engineering & Science
Last Modified:	04 Mar 2022 13:07
URI:	http://gala.gre.ac.uk/id/eprint/18104

Actions (login required)

View Item

Downloads