Bilkent University
Department of Computer Engineering

Simultaneous Embedding and Visualization of Related Graphs


Cesim Erten

University of Arizona
Computer Science Department
Tuscon, AZ, USA


Graph embedding and visualization problems arise in relational information visualization. The two primary goals in graph visualization are drawings that convey the relationships in the underlying data and drawings that are aesthetically pleasing. Often, we have a series of related graphs that we would like to compare. These graphs may come from Software Engineering where we have inheritance graphs, data flow diagrams, or call graphs that evolve over the course of code development, giving rise to different graphs each time. Similarly, in Evolutionary Biology different hypotheses/models produce different phylogenetic trees on the same set of organisms. In this talk we focus on the problem of simultaneous embedding and visualization of graphs. We will describe the system we developed for simultaneous visualization of general graphs, and its application to the visualization of Computer Science Literature as an evolving structure. We will show how animation/morphing can aid simultaneous visualization of general graphs and describe a mental-map preserving technique for morphing plane drawings. Finally, we will discuss simultaneous embedding results for the case where the input graphs are planar and present algorithms for special cases resulting with area bounded drawings of related graphs.

DATE: April 14, 2004, Wednesday @ 13:40