Graphs are a very commonly used information structure, and have been applied to a broad range of fields from computer science to biology. There are several important issues to consider when designing graph visualizations. One of the most difficult problems researchers face is how to visualize large graphs. While an algorithm may produce good layouts for graphs of several hundred nodes, it may not scale well to several thousand nodes. And, as the size of the graph increases, performance will degrade rapidly, making it difficult to build an interactive system. Label readability will also suffer, hindering users' abilities to understand the graph data and perform many tasks. Finally, even if a system can lay out and display large graphs, the cognitive demands placed on the user by the visualization may be overwhelming.

This dissertation describes and applies several design principles to various graph visualization domains to address these issues. Tightly-coupled and highly customized views were used for graph visualization in a novel way. A new tree layout approach to graph visualization was proposed with appropriate visualization and interaction techniques. When visualizing graphs as trees, a guiding metaphor "Plant a seed and watch it grow" was used to support information gathering and detailed exploration of the graph's local structure.

Three graph visualization systems guided by these design principles were also developed and evaluated. First, PaperLens provides an abstract overview of the full dataset and shows relationships through interactive highlighting. It offers a novel alternative to the more common node-link diagram approach to graph visualization. Second, the development and evaluation of TaxonTree provided valuable insights that led to the design of TreePlus, a general interactive graph visualization component. Finally, TreePlus takes a tree layout approach to graph visualization, transforming a graph into a tree plus cross links (the links not represented by the spanning tree) using visualization, animation and interaction techniques to reveal the graph structure while preserving the label readability.

Other contributions of this work include the development of a task taxonomy for graph visualization and several specific applications of the graph visualization systems described above.