# ICS 269, Spring 2005: Theory Seminar

## 25 Feb 2005:

Visualizing Evolving Graphs by Simultaneous Embeddings

Speaker: Stephen Kobourov,
Department of Computer Science,
University of Arizona

Abstract:
Traditional problems in graph visualization involve the layout of a
single graph, while problems in simultaneous graph visualization
involve the layout of multiple related graphs. A series of related
graphs may arise from one relation between a set of objects as it
evolves through time or from several relationships defined on the same
set of objects. In simultaneous graph embedding, nodes are placed in
the exact same locations in all the graphs and a series of graphs are
simultaneously embedable if it is possible to find locations that
yield straight-line crossing-free drawings for each of the individual
graphs. We present polynomial time algorithms for simultaneous
embedding of various classes of planar graphs and prove that some
classes of graphs cannot be simultaneously embedded. Further, we
present a near-linear time algorithm for visualizing graphs that
evolve through time and demonstrate its application to problems in
software engineering and databases.

VITA:
Stephen Kobourov is an Assistant Professor at the University of
Arizona. His research interests include information visualization,
graph drawing, and geometric algorithms, emphasizing problems relating
to graph visualization. He received a BS in Computer Science and
Mathematics from Dartmouth College, and MS and PhD in Computer Science
from Johns Hopkins University.