Graph & Tree Drawing

Project Mission

Graphs and trees are a natural model for the underlying data associated with countless scientific and data analysis problems. And for other problems, graphs and trees can sometimes provide a intuitive interface for the data exploration process. The graph- and tree-related research in the VIDI lab aims to advance the state of the art regarding the speed and quality of layout, and to provide novel methods of both interacting with and through such visual structures.

People Involved

Zeqian Shen, Ph.D. candidate, VIDI

Chris Muelder, Ph.D. student, VIDI

Anna Tikhonova, Ph.D. student, VIDI

Kwan-Liu Ma, Professor, VIDI

A Study of Layout, Rendering, and Interaction Methods for Immersive Graph Visualization
Oh-Hyun Kwon, Chris W. Muelder, Kyungwon Lee, and Kwan-Liu Ma
IEEE Transactions on Visualization and Computer Graphics
Volume 22, Number 7, July, 2016, pp. 1802--1815
Information visualization has traditionally limited itself to 2D representations, primarily due to the prevalence of 2D displays and report formats. However, there has been a recent surge in popularity of consumer grade 3D displays and immersive head-mounted displays (HMDs). The ubiquity of such displays enables the possibility of immersive, stereoscopic visualization environments. While techniques that utilize such immersive environments have been explored extensively for spatial and scientific visualizations, contrastingly very little has been explored for information visualization. In this paper, we present our considerations of layout, rendering, and interaction methods for visualizing graphs in an immersive environment. We conducted a user study to evaluate our techniques compared to traditional 2D graph visualization. The results show that participants answered significantly faster with a fewer number of interactions using our techniques, especially for more difficult tasks. While the overall correctness rates are not significantly different, we found that participants gave significantly more correct answers using our techniques for larger graphs. ...
[ PDF ] [ BibTeX ] [ Project Page ]
An Incremental Layout Method for Visualizing Online Dynamic Graphs
Tarik Crnovrsanin, Jacqueline Chu, and Kwan-Liu Ma
In Proceedings of The 23rd International Symposium on Graph Drawing and Network Visualization
In Proceedings of the 23rd International Symposium on Graph , September, 2015, pp. 16--29
Graphs provide a visual means for examining relation data and force-directed methods are often used to lay out graphs for viewing. Making sense of a dynamic graph as it evolves over time is challenging, and previous force-directed methods were designed for static graphs. In this paper, we present an incremental version of a multilevel multi-pole layout method with a refinement scheme incorporated, which enables us to visualize online dynamic networks while maintaining a mental map of the graph structure. We demonstrate the effectiveness of our method and compare it to previous methods using several network data sets. ...
[ PDF ] [ BibTeX ]
Spherical Layout and Rendering Methods for Immersive Graph Visualization
Oh-Hyun Kwon, Chris W. Muelder, Kyungwon Lee, and Kwan-Liu Ma
In Proceedings of IEEE PacificVis Visualization Notes
April, 2015
While virtual reality has been researched in many ways for spatial and scientific visualizations, comparatively little has been explored for visualizations of more abstract kinds of data. In particular, stereoscopic and VR environments for graph visualization have only been applied as limited extensions to standard 2D techniques (e.g. using stereoscopy for highlighting). In this work, we explore a new, immersive approach for graph visualization, designed specifically for virtual reality environments ...
[ PDF ] [ BibTeX ]
Visualization Techniques for Categorical Analysis of Social Networks with Multiple Edge Sets
Tarik Crnovrsanin, Chris W. Muelder, Robert Faris, Diane Felmlee, and Kwan-Liu Ma
Social Networks
Volume 37, 2014, pp. 56-64
The growing popularity and diversity of social network applications present new opportunities as well as new challenges. The resulting social networks have high value to business intelligence, sociological studies, organizational studies, epidemical studies, etc. The ability to explore and extract information of interest from the networks is thus crucial. However, these networks are often large and composed of multi-categorical nodes and edges, making it diffcult to visualize and reason with conventional methods. In this paper, we show how to combine statistical methods with visualization to address these challenges, and how to arrange layouts differently to better bring out different aspects of the networks. We applied our methods to several social networks to demonstrate their e effectiveness in characterizing the networks and clarifying the structures of interest, leading to new findings. ...
[ PDF ] [ BibTeX ]
Multivariate Social Network Visual Analytics
Chris W. Muelder, Liang Gou, Kwan-Liu Ma, and Michelle X. Zhou
Multivariate Network Visualization. Lecture Notes in Computer Science, 8380. Springer-Verlag
3, Multivariate Network Visualization. Lecture Notes in Computer Science, 8380. Springer-Verlag, 2014
Social networks are one of the most common type of multivariate networks. In this chapter, we describe the data characteristics of multivariate social networks and various types of tasks for understanding and analyzing such networks. We also present a set of example visual analytic technologies that are developed to support different types of social network analysis. Finally, we discuss remaining challenges and future research directions. ...
[ PDF ] [ BibTeX ]
Temporal Multivariate Networks
James Abello, Daniel Archambault, Jessie Kennedy, Stephen Kobourov, Kwan-Liu Ma, Silvia Miksch, Chris W. Muelder, and Alexandru Telea
Multivariate Network Visualization. Lecture Notes in Computer Science, 8380. Springer-Verlag
8, Multivariate Network Visualization. Lecture Notes in Computer Science, 8380. Springer-Verlag, 2014
[ PDF ] [ BibTeX ]
Egocentric Storylines for Visual Analysis of Large Dynamic Graphs
Chris W. Muelder, Tarik Crnovrsanin, and Kwan-Liu Ma
In Proceedings of 1st IEEE Workshop on Big Data Visualization (BigDataVis)
Oct, 2013, pp. 56-62
Large dynamic graphs occur in many fields. While overviews are often used to provide summaries of the overall structure of the graph, they become less useful as data size increases. Often analysts want to focus on a specific part of the data according to domain knowledge, which is best suited by a bottom-up approach. This paper presents an egocentric, bottom-up method to exploring a large dynamic network using a storyline representation to summarize localized behavior of the network over time. ...
[ PDF ] [ BibTeX ]
Large-Scale Graph Visualization and Analytics
Kwan-Liu Ma and Chris W. Muelder
IEEE Computer
Volume 46, Number 7, July, 2013, pp. 39-46
Novel approaches to network visualization and analytics use sophisticated metrics that enable rich interactive network views and node grouping and filtering. A survey of graph layout and simplification methods reveals considerable progress in these new directions. ...
[ PDF ] [ BibTeX ]
A Visual Network Analysis Method for Large Scale Parallel I/O Systems
Carmen Sigovan, Chris W. Muelder, Kwan-Liu Ma, Jason Cope, Kamil Iskra, and Robert Ross
In Proceedings of 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS)
may, 2013, pp. 308-319
Parallel applications rely on I/O to load data, store end results, and protect partial results from being lost to system failure. Parallel I/O performance thus has a direct and significant impact on application performance. Because supercomputer I/O systems are large and complex, one cannot directly analyze their activity traces. While several visual or automated analysis tools for large-scale HPC log data exist, analysis research in the high-performance computing field is geared toward computation performance rather than I/O performance ...
[ PDF ] [ BibTeX ]
Improved Cluster Tracking for Visualization of Large Dynamic Graphs
Chris W. Muelder, Arnaud Sallaberry, and Kwan-Liu Ma
In Proceedings of 13e Conférence Francophone sur l'Extraction et la Gestion des Connaissances
Jan, 2013, pp. 21-32
Analysis and visualization of dynamic graphs is a challenging problem. Clustering can be applied to dynamic graphs in order to generate interactive visualizations with both high stability and good layout quality. However, the existing implementation is naïve and unoptimized. Here we present new algorithms to improve both the temporal clustering results and the efficiency of the cluster tracking calculation, and evaluate the results and performance. ...
[ PDF ] [ BibTeX ]
Clustering, Visualizing, and Navigating for Large Dynamic Graphs
Arnaud Sallaberry, Chris W. Muelder, and Kwan-Liu Ma
In Proceedings of the 20th International Conference on Graph Drawing
Sepetember, 2012, pp. 487-498
In this paper, we present a new approach to exploring dynamic graphs. We first propose a new clustering algorithm for dynamic graphs which nds an ideal clustering for each time-step and links the clusters together. The resulting time-varying clusters are then used to defi ne two visual representations. The rst view is an overview that shows how clusters evolve over time and provides an interface to find and select interesting time-steps ...
[ PDF ] [ BibTeX ]
Ambiguity-Free Edge-Bundling for Interactive Graph Visualization
sheng-Jie Luo, Chun-Liang Liu, Bing-Yu Chen, and Kwan-Liu Ma
IEEE Transactions on Visualization and Computer Graphics
Graph visualization has been widely used to understand and present both global structural and local adjacency information in relational datasets (e.g., transportation networks, citation networks, or social networks). Large graphs, however, are difficult to visualize because fast layout and good clarity are not always easily achieved. When the number of edges is large, edge bundling can be used to improve the clarity, but in many cases, the edges could be still too cluttered to permit correct interpretation of the relations between nodes ...
[ PDF ] [ BibTeX ] [ Project Page ]
Content Based Graph Visualization of Audio Data for Music Library Navigation
Chris W. Muelder, Thomas Provan, and Kwan-Liu Ma
In Proceedings of IEEE International Symposium on Multimedia (ISM)
December, 2010, pp. 129-136
As a user's digital music collection grows, it can become difficult to navigate. Music library programs aid in this task by organizing music according to tags such as artist or title. However these generally utilize a text based interface, and they do not take into account the content of the music itself. As such, they do not handle untagged or mistagged music well. Automated metrics exist, but are not as widely used since they have the potential to be unreliable. This paper presents a graph-based visual interface for exploring a library of music based on analysis of the content of the music rather than tag information, which allows the user to navigate a music library thematically. ...
[ PDF ] [ BibTeX ]
A Hybrid Space-Filling and Force-Directed Layout Method for Visualizing Multiple-Category Graphs
Takayuki Itoh, Chris W. Muelder, Kwan-Liu Ma, and Jun Sese
In Proceedings of IEEE Pacific Visualization Symposium
April, 2009, pp. 121-128
Many graphs used in real-world applications consist of nodes belonging to more than one category. We call such graph ”multiplecategory graphs”. Social networks are typical examples of multiplecategory graphs: nodes are persons, links are friendships, and categories are communities that the persons belong to. It is often helpful to visualize both connectivity and categories of the graphs simultaneously. In this paper, we present a new visualization technique for multiple-category graphs ... ...
[ PDF ] [ BibTeX ]
Rapid Graph Layout Using Space Filling Curves
Chris W. Muelder and Kwan-Liu Ma
In Proceedings of IEEE Conference on Information Visualization (InfoVis)
2008, pp. 1301-1308
Network data frequently arises in a wide variety of fields, and node-link diagrams are a very natural and intuitive representation of such data. In order for a node-link diagram to be effective, the nodes must be arranged well on the screen. While many graph layout algorithms exist for this purpose, they often have limitations such as high computational complexity or node colocation. This paper proposes a new approach to graph layout through the use of space filling curves which is very fast and guarantees that there will be no nodes that are colocated. The resulting layout is also aesthetic and satisfies several criteria for graph layout effectiveness. ...
[ PDF ] [ BibTeX ]
A Scalable Parallel Force-Directed Graph Layout Algorithm
Anna Tikhonova and Kwan-Liu Ma
In Proceedings of Eurographics Parallel Graphics and Visualization Symposium (EGPGV 2008)
April, 2008, pp. 25-32
Understanding the structure, dynamics, and evolution of large graphs is becoming increasingly important in a variety of fields. The demand for visual tools to aid in this process is rising accordingly. Yet, many algorithms that create good representations of small and medium-sized graphs do not scale to larger graph sizes. The exploitation of the massive computational power provided by parallel and distributed computing is a natural progression for handling important problems such as large graph layout ...
[ PDF ] [ BibTeX ]
A Treemap Based Method for Rapid Layout of Large Graphs
Chris W. Muelder and Kwan-Liu Ma
In Proceedings of IEEE Pacific Visualization Symposium
Mar, 2008
Abstract graphs or networks are a commonly recurring data type in many fields. In order to visualize such graphs effectively, the graph must be laid out on the screen coherently. Many algorithms exist to do this, but many of these algorithms tend to be very slow when the input graph is large. This paper presents a new approach to the large graph layout problem, which quickly generates an effective layout. This new method proceeds by generating a clustering hierarchy for the graph, applying a treemap to this hierarchy, and finally placing the graph vertices in their associated regions in the treemap. It is ideal for interactive systems where operations such as semantic zooming are to be performed, since most of the work is done in the initial hierarchy calculation, and it takes very little work to recalculate the layout. This method is also valuable in that the resulting layout can be used as the input to an iterative algorithm (e.g., a force directed method), which greatly reduces the number of iterations required to converge to a near optimal layout. ...
[ PDF ] [ BibTeX ]
Path Visualization for Adjacency Matrices
Zeqian Shen and Kwan-Liu Ma
In Proceedings of Eurographics/IEEE VGTC Syposium on Visualization
May, 2007, pp. 83-90
For displaying a dense graph, an adjacency matrix is superior than a node-link diagram because it is more compact and free of visual clutter. A node-link diagram, however, is far better for the task of path finding because a path can be easily traced by following the corresponding links, provided that the links are not heavily crossed or tangled.We augment adjacency matrices with path visualization and associated interaction techniques to facilitate path finding. ...
[ PDF ] [ BibTeX ]
Visual Analysis of Large Heterogeneous Social Networks by Semantic and Structure
Zeqian Shen, Kwan-Liu Ma, and Tina Eliassi-Rad
IEEE Transactions on Visualization and Computer Graphics
Volume 12, Number 6, December, 2006, pp. 1427-1439
Social network analysis is an active area of study beyond sociology. It uncovers the invisible relationships between actors in a network and provides understanding of social processes and behaviors. It has become an important technique in a variety of application areas such as the Web, organizational studies, and homeland security. This paper presents a visual analytics tool, OntoVis, for understanding large, heterogeneous social networks, in which nodes and links could represent different concepts and relations, respectively ...
[ PDF ] [ BibTeX ]
Evaluating the Effectiveness of Tree Visualization Systems for Knowledge Discovery
Yue Wang, Soon Tee Teoh, and Kwan-Liu Ma
In Proceedings of Eurographics Visualization Symposium
May, 2006, pp. 67-74
User studies, evaluations, and comparisons of tree visualization systems have so far focused on questions that can readily be answered by simple, automated queries without needing visualization. Studies are lacking on the actual use of tree visualization in discovering intrinsic, hidden, non-trivial and potentially valuable knowledge. We have thus formulated a set of tree exploration tasks not previously considered and have performed user studies and analysis to determine how visualization helps users to perform these tasks ...
[ PDF ] [ BibTeX ]
BiblioViz: A System for Visualizing Bibliography Information
Zeqian Shen, Michael Ogawa, Soon Tee Teoh, and Kwan-Liu Ma
In Proceedings of 2006 Asia-Pacific Symposium on Information Visualization
February, 2006, pp. 93-102
The InfoVis 2004 contest led to the development of several bibliography visualization systems. Even though each of these systems offers some unique views of the bibliography data, there is no single best system offering all the desired views. We have thus studied how to consolidate the desirable unctionalities of these systems into a cohesive design. We have also designed a few novel visualization methods ...
[ PDF ] [ BibTeX ]
Discovering Parametric Clusters in Social Small-World Graphs
Johnathan McPherson, Kwan-Liu Ma, and Michael Ogawa
In Proceedings of ACM Symposium on Applied Computing
March, 2005, pp. 1231-1238
We present a strategy for analyzing large, social small-world graphs, such as those formed by human networks. Our approach brings together ideas from a number of different research areas, including graph layout, graph clustering and partitioning, machine learning, and user interface design. It helps users explore the networks and develop insights concerning their members and structure that may be difficult or impossible to discover via traditional means, including existing graph visualization and/or statistical methods ...
[ PDF ] [ BibTeX ]
MoireGraphs: Radial Focus+Context Visualization and Interaction for Graphs with Visual Nodes
T.J. Jankun-Kelly and Kwan-Liu Ma
In Proceedings of 2003 Symposium on Information Visualization
October, 2003, pp. 8-15
Graph and tree visualization techniques enable interactive exploration of complex relations while communicating topology. However, most existing techniques have not been designed for situations where visual information such as images is also present at each node and must be displayed. This paper presents MoireGraphs to address this need. MoireGraphs combine a new focus+context radial graph layout with a suite of interaction techniques (focus strength changing, radial rotation, level highlighting, secondary foci, animated transitions and node information) to assist in the exploration of graphs with visual nodes ...
[ PDF ] [ BibTeX ]
PaintingClass: Interactive Construction, Visualization and Exploration of Decision Trees
Soon Tee Teoh and Kwan-Liu Ma
In Proceedings of 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2003)
August, 2003, pp. 667-672
Decision trees are commonly used for classification. We propose to use decision trees not just for classification but also for the wider purpose of knowledge discovery, because visualizing the decision tree can reveal much valuable information in the data. We introduce PaintingClass, a system for interactive construction, visualization and exploration of decision trees. PaintingClass provides an intuitive layout and convenient navigation of the decision tree ...
[ PDF ] [ BibTeX ]
RINGS: A Technique for Visualizing Large Hierarchies
Soon Tee Teoh and Kwan-Liu Ma
In Proceedings of Graph Drawing Conference
April, 2002, pp. 268-275
We present RINGS, a technique for visualizing large trees with hundreds of thousands of nodes. We introduce a new ringed circular layout of nodes to make more efficient use of limited display space. RINGS provides the user with the means to specify areas of primary and secondary focus, and is able to show multiple foci without compromising understanding of the graph ...
[ PDF ] [ BibTeX ]
Back to Page Top