|
Activity Number:
|
225
|
|
Type:
|
Invited
|
|
Date/Time:
|
Tuesday, August 8, 2006 : 8:30 AM to 10:20 AM
|
|
Sponsor:
|
Section on Statistical Graphics
|
| Abstract - #305061 |
|
Title:
|
Visualizing Evolving Graphs by Simultaneous Embeddings
|
|
Author(s):
|
Stephen G. Kobourov*+
|
|
Companies:
|
University of Arizona
|
|
Address:
|
Department of Computer Science, Tucson, AZ, 85721,
|
|
Keywords:
|
graph drawing ; information visualization ; evolving graphs
|
|
Abstract:
|
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 embedding, nodes are placed in the exact same locations in all the graphs, and a series of graphs is simultaneously embeddable if it is possible to find node locations that yield straight-line, crossing-free drawings for each of the graphs. We present polynomial time algorithms for simultaneous embedding of various classes of planar graphs and prove some classes of graphs cannot be embedded simultaneously. 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.
|
- The address information is for the authors that have a + after their name.
- Authors who are presenting talks have a * after their name.
Back to the full JSM 2006 program |
