Skip to main content

A Method for Graph Drawing Utilising Patterns

Baker, Robert (2017) A Method for Graph Drawing Utilising Patterns. Doctor of Philosophy (PhD) thesis, University of Kent,.

Abstract

This thesis describes a novel method for the layout of undirected graphs. It works by identifying certain patterns within the graph and drawing these in a consistent manner. For graphs to be useful and of benefit to a user, the result must clear and easy to understand. This process attempts to draw graphs in such a manner. Firstly, a background of graph problems and graph drawing is introduced, before the benefits of patterns are explained. Following this, there is an in-depth discussion of a number of existing graph drawing techniques, perceptual theories and methods for subgraph isomorphism. This pattern-based method is then explained in great detail. Firstly, the patterns required are defined and examples given. Then, there is an explanation of the methodology involved in identifying these patterns within a graph. Following on from this, the order in which patterns are drawn based on their connection types to those already drawn is detailed, before a detailed description of each drawing method. Evaluation of this method follows, starting with analysis mainly based on three real world data sources. This is in the form of side-by-side comparisons of graphs drawn with this method and a force-directed method. Following this, a metric based evaluation compares the two methods on edge crossings and occlusion, while also detailing some pattern based metrics. Further evaluation continues in the form of an empirical study. The methodology of this study is detailed before results are displayed. Analysis of these results follows, with conclusions drawn. Finally, potential further work is detailed and possible implementations discussed. All study materials and results are provided in the Appendix for those who wish to repeat the study or analysis.

Item Type: Thesis (Doctor of Philosophy (PhD))
Thesis advisor: Rodgers, Peter
Thesis advisor: Thompson, Simon
Thesis advisor: Barnes, David
Uncontrolled keywords: graph-drawing subgraph-isomorphism information-visualization
Divisions: Faculties > Sciences > School of Computing
SWORD Depositor: System Moodle
Depositing User: System Moodle
Date Deposited: 06 Oct 2017 14:39 UTC
Last Modified: 29 May 2019 19:40 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/63895 (The current URI for this page, for reference purposes)
  • Depositors only (login required):

Downloads

Downloads per month over past year