A Multilevel Approach for Event-Based Dynamic Graph Drawing

Abstract

The timeslice is the predominant method for drawing and visualizing dynamic graphs. However, when nodes and edges have real coordinates along the time axis, it becomes difficult to organize them into discrete timeslices, without a loss of temporal information due to projection. Event-based dynamic graph drawing rejects the notion of a timeslice and allows each node and edge to have its own real-valued time coordinate. Nodes are represented as trajectories of adaptive complexity that are drawn directly in the three-dimensional space-time cube (2D + t). Existing work has demonstrated clear advantages for this approach, but these advantages come at a running time cost. In response to this scalability issue, we present MultiDynNoS, the first multilevel approach for event-based dynamic graph drawing. We consider three operators for coarsening and placement, inspired by Walshaw, GRIP, and FM3, which we couple with an event-based graph drawing algorithm. We evaluate our approach on a selection of real graphs, showing that it outperforms timeslice-based and existing event-based techniques.