Novel Techniques for Visualization of Graphs and Trees

Graph data, especially large graph data, come up in many domains, such as social networks, the map of science, biological data, and even knitting! This presents a problem when we consider visualizing these structures. Layouts must be chosen carefully so that the structure of the graph is visible. Some graphs are large enough and connected enough so that adding all edges and nodes creates an unreadable hairball. In this paper, we look at several domains and work towards readable graphs. We begin with drawing large trees in a readable way. The process begins with converting a graph to a tree. This tree is laid out with no label overlaps, no edge crossings, and compactly. A user interface utilizing this layout is provided that further facilitates users' understanding of large networks. Semantic zooming and clustering methods allow users to work from their knowledge of map systems, such as Google maps to explore new, graph data. Here, we branch into dynamic trees and planar graphs. In our evolving tree setting, nodes and edges enter the graph, we make sure no edge crossings are introduced, the layout is compact, and the nodes are relatively stable. In the planar setting, we look at a specific class of graphs, those that correspond to simple knitting patterns. These graphs have defined edge lengths that correspond to the physical knitting. We lay these out in a similar manner as above, making sure no edge crossings are introduced. We will discuss each of these domains and work towards graph readability. The first chapter gives an introduction to the problem, describes related work, and lays out our contributions. It contains a few sections on work related to trees, dynamic trees, and planar graphs. The next chapter is dedicated to discussing an algorithm for laying out readable trees. In the next chapter, we discuss a user interface that utilizes this layout to give semantic zooming and readability at every level. From here, we expand in the next chapter to discuss evolving trees, moving our readable layouts into a dynamic realm. In the fifth chapter, we discuss planar graph layouts in the context of knitting graphs. In the final chapter, we discuss future work and conclusions. [The dissertation citations contained here are published with the permission of ProQuest LLC. Further reproduction is prohibited without permission. Copies of dissertations may be obtained by Telephone (800) 1-800-521-0600. Web page: http://www.proquest.com/en-US/products/dissertations/individuals.shtml.]