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.