White Rose University Consortium logo
University of Leeds logo University of Sheffield logo York University logo

Navigating networks using overlays

Myers, Colin Stephen (2013) Navigating networks using overlays. PhD thesis, University of Leeds.

Available under License Creative Commons Attribution-Noncommercial-Share Alike 2.0 UK: England & Wales.

Download (11Mb) | Preview


This thesis contributes a novel approach to navigation tasks in large graphs. Graph visualization is the problem of representing the structure of a mathematical graph G = (V,E), V a set of vertices (or nodes) and E ⊆V ×V a set of edges. My work is concerned with the node-link representation of graphs and I use the term network to distinguish this external representation from the underlying mathematical structure. Networks are an intuitive representation of a set of elements and the relationships between them, and are known to be effective for analysis tasks involving following paths between nodes. I define navigation as the task of identifying and following such a path in display space. Unfortunately the utility of a network diminishes as the density of edges increases and edge-crossings make navigation taxing. A well-explored approach to this problem is to find a perspicuous layout of the nodes. While this improves the readability of individual nodes and edges it may also require a compromise: to be easily understood the overall arrangement of the network should also correspond with the user’s internal mental model of the domain, a property referred to as congruence. Other solutions distort the display space or use multiple-scaled-views to promote comprehension of local details while retaining awareness of the global context, but often lack direct support for navigation of the network topology beyond the local context. This thesis contributes a model of visual graph analysis that brings together recent advances in cartographic representation, diagram comprehension, and graph visualization, leading to a greater understanding of network navigation bottlenecks in terms of the degree of correspondence between the external graph representation, and the user’s ‘mental map’. Motivated by this model I present a new approach to graph visualization that separates concerns of navigation from those of depiction with the aim of improving correspondence between the internal and external representations. I describe the design and realization of an interface for network navigation inspired by the new approach within a pipeline-based architecture, and provide a reflective evaluation of the implementation.

Item Type: Thesis (PhD)
ISBN: 978-0-85731-409-3
Academic Units: The University of Leeds > Faculty of Engineering (Leeds) > School of Computing (Leeds)
Identification Number/EthosID: uk.bl.ethos.589337
Depositing User: Repository Administrator
Date Deposited: 23 Jan 2014 15:57
Last Modified: 07 Mar 2014 11:48
URI: http://etheses.whiterose.ac.uk/id/eprint/5055

You do not need to contact us to get a copy of this thesis. Please use the 'Download' link(s) above to get a copy.
You can contact us about this thesis. If you need to make a general enquiry, please see the Contact us page.

Actions (repository staff only: login required)