A graph consists of a set and a binary relation on that set. Each element
of the set is a node of the graph, while each element of the binary relation
is an edge of the graph that encodes a relationship between two nodes.
Graph are pervasive in many areas of science, engineering, and the social
sciences: servers on the Internet are connected, proteins interact in large
biological systems, social networks encode the relationships between people,
and functions call each other in a program. In these domains, the graphs
can become very large, consisting of hundreds of thousands of nodes and
millions of edges.
Graph drawing approaches endeavour to place these nodes in two or
three-dimensional space with the intention of fostering an understanding
of the binary relation by a human being examining the image. However,
many of these approaches to drawing do not exploit higher-level structures
in the graph beyond the nodes and edges. Frequently, these structures can
be exploited for drawing. As an example, consider a large computer network
where nodes are servers and edges are connections between those servers.
If a user would like understand how servers at UBC connect to the rest of
the network, a drawing that accentuates the set of nodes representing those
servers may be more helpful than an approach where all nodes are drawn in
the same way. In a feature-based approach, features are subgraphs exploited
for the purposes of drawing. We endeavour to depict not only the binary
relation, but the high-level relationships between features.
This thesis extensively explores a feature-based approach to graph vi
sualization and demonstrates the viability of tools that aid in the visual
ization of large graphs. Our contributions lie in presenting and evaluating
novel techniques and algorithms for graph visualization. We implement five
systems in order to empirically evaluate these techniques and algorithms,
comparing them to previous approaches.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:BVAU./2839 |
| Date | 11 1900 |
| Creators | Archambault, Daniel William |
| Publisher | University of British Columbia |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Format | 8716543 bytes, application/pdf |
Page generated in 0.0022 seconds