A Search Set Model of Path Tracing in Graphs

Jessica Q. Dawson

Abstract | Paper | Talk |
Example of the user study interface. Graphs were displayed on a Wacom Cintiq tablet screen, and participants hovered over nodes with the pen to demonstrate their search process as they completed the study task.


Path tracing is a common task in many real world uses of graphs that display networks of relationships. Despite previous work in the evaluation of how factors, such as edge-edge crossings, impact the readability of graph layouts, what makes one path-tracing task more difficult than another is not well understood.

To address this question we conducted an observational user study with 12 participants completing a path-tracing task. Our extensive qualitative analysis of the study data led to a detailed characterization of common path-tracing behaviours. We then created a predictive model of the paths that users are most likely to search, which we name the search set, based on the behaviours we observed. To validate our predictive behavioural model, and to demonstrate how the search set could be used, we conducted a careful comparison of graph readability factors through a hierarchical multiple regression analysis.


A Search Set Model of Path Tracing In Graphs.
M.Sc. Thesis,Dept. of Computer Science, University of British Columbia, October 2013.

M.Sc. Presentation

Talk given at UBC Computer Science in fulfillment of degree requirements:
[PDF (12.2 MB)]

Jessica Dawson
Last modified: Dec 5, 2013