Back to search

University of British Columbia

Low-stretch trees for network visualization

Abstract

dc:description

Low-stretch trees are spanning trees which provide approximate distance preservation for edges in the original graph by minimizing stretch. We explore the application of these trees to network visualization. In particular, we present a novel edge bundling technique, LSTB, that computes edge bundles explicitly and efficiently and does not rely on fixed vertex positions. This approach is in contrast to previous methods, which require the user to provide a layout of the input graph. We introduce an abstract framework for edge bundling methods, which provides a unifying formalization of bundling terminology and techniques, as well as a classification of such methods. Based on this framework, LSTB provides algorithmic support for sophisticated visual encodings, including dynamic layout adjustment and interactive bundle querying. In addition, we explore the use of the multiplicative weights update method to compute a distribution over low-stretch trees in order to achieve low stretch for all edges in expectation, rather than on average. We present the results of using this distribution in place of a single low-stretch tree as a routing graph for LSTB. While the distribution provides better stretch guarantees, we find that from a visual perspective a single low-stretch tree provides a better routing graph for the LSTB edge bundling application.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2015

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • McKnight, Rebecca Linda

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivs 2.5 Canada
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/54490

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

McKnight, Rebecca Linda. Low-stretch trees for network visualization. master's thesis, University of British Columbia, 2015. http://hdl.handle.net/2429/54490