Advanced visualization, navigation, and interaction in graphs: theory, design, and evaluation

Graph visualization is one of the most common sub-fields of information visualization as graphs appear in numerous daily life applications such as social networks, web browsing, computer file systems, airline networks, and data structures. Graph visualization uses graphical representations of these networks to show relationship structures, allowing easy analysis, finding key nodes, etc. Realistic graphs are generally large in size; for example, Facebook or Twitter social networks are graphs consisting of millions of nodes and edges. In fact, these graphs are often so large that they cannot be seen all at once. Using interactive visualization to create graphical representations of these graphs is one approach, but the graphs are still too large to show entirely, and only a portion of them will be visible on the screen at any point in time. Also, nowadays many new types of graphs like dynamic graphs (that varies with time), multimodal graphs (where nodes or edges have different types), multivariate graphs (that have attributes associated to nodes or edges), knowledge networks (where nodes or edges have text attributes), etc are evolving and novel visualization and interaction techniques are needed to analyze them. Therefore, the main purposes of this thesis are: 1. Design, build, and evaluate navigation and interaction techniques that help users to gain insight and build a better mental map for large graphs navigation. 2. Design novel visualization and navigation techniques for new types of graph (dynamic graphs, multimodal graphs, and knowledge networks) arising in the field. 3. Build a pipeline to convert any relational datasets into graphs, and generalize our techniques to visualize and interact with these datasets. We first define a design space for classifying the existing techniques as well as designing new visualization or interaction techniques for graphs. Based on this design space, we design a set of graph visualization and navigation techniques. These techniques are then evaluated in the form of user studies where we show that our designed techniques are more efficient, more accurate, and perform better than current standard techniques. We give other applications as well; for example, maps, social networks, and databases, where our techniques are helpful.