Colloquium Speaker

Speaker: 
Cesim Erten
Topic: 
Simultaneous Embedding and Visualization of Graphs
Date: Thursday, March 4
Time: 11:00AM
Place: Gould-Simpson, Room 701
Refreshments will be served in the 7th floor lobby of Gould-Simpson at 10:45 AM

Abstract

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. The aesthetic criteria are the topic of much debate and research, but some generally accepted and tested standards include preference for straight-line edges or those with only a few bends, a limited number of crossings, good separation of vertices and edges, as well as a small drawing area. Often, we have a series of related graphs that we would like to compare visually. These graphs may come from social network analysis, where different relationships among the same set of people are being studied. Similarly, in biology, different algorithms produce different philogenetic trees on the same set of organisms. Finally, we may be studying an evolving relationship, represented by graphs that change over the course of time. In this talk we focus on the problem of simultaneous embedding and visualization of graphs. We will describe theoretical results and algorithms for the case where the input graphs are planar and show that even in very simple cases some aesthetic criteria might not be met. We will show how to simultaneously embed some special classes of planar graphs such as paths, cycles, and caterpillars on an $O(n)$ by $O(n)$ integer grid. We will also show that some classes of graphs such as outer planar graphs may not admit such embeddings. We will describe how morphing can be useful in simultaneous visualizations and an algorithm to morph a planar drawing into another without creating any crossings. We will then focus our attention to heuristic layout algorithms and visualization models we designed to solve the problem in general and present the systems we developed.