| Résumé | 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.
In this talk, I describe a feature-based approach to graph
visualization and demonstrate the viability of tools that
aid in the visualization 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.
|