Navigating networks using overlays

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.