TITLE: Visualizing Evolving Graphs

SPEAKER: Stephen Kobourov, 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. We present efficient algorithms for simultaneous
embedding of various classes of planar graphs and prove that some
classes of graphs cannot be simultaneously embedded. We also present 
efficient algorithms for visualizing graphs that evolve through time 
and demonstrate application to problems in software engineering.

Next we consider alternatives to the standard node-link diagrams. 
Such traditional graph visualization methods often fail to capture 
the underlying structural information, clustering, and neighborhoods. 
Our algorithm for visualizing graphs as maps provides a way to overcome 
some of the shortcomings with the help of the geographic map metaphor. 
While graphs, charts, and tables often require considerable effort to 
comprehend, a map representation is more intuitive, as most people are 
very familiar with maps and even enjoy carefully examining maps. The 
effectiveness of the algorithm is illustrated with examples from several domains: 
TV shows, movies, books, and music.