Summary

Dynamic graph layout addresses some interesting problems in information visualization: navigation in large graphs, display of dynamic data represented by graphs, and interactive graph editing. We will discuss some current problems in dynamic graph layout and the engineering of a interactive layout system.

Motivation

Graph drawing is an effective way of visualizing relationships between objects. Considerable progress has been achieved in automated graph layout. The types of layout algorithms that have succeeded in practice include:

• Hierarchical layout (upward drawings, cone trees) [HL91, STT81, GKNV93, RMC93]
• Physical simulation [FCW67, E84, KK89, EW93] and principal components analysis [KS80]
• Orthogonal layout combined with planarization [T90]

Current graph drawing systems usually employ static (batch) layout algorithms. Although static layout is useful in many applications, stable dynamic layout seems to be essential in other situations:

Incremental navigation in large graphs. There is considerable interest in browsing large graphs that represent vast computer networks, linked hypertext documents, etc. Even aside from technical limitations such as display size and resolution, conventional layouts of large graphs usually offer, at best, only an overview of global properties such as a size, density, diameter, etc. Identifying individual elements and relationships ( "detail-in-context") is usually quite difficult.

Geometric fisheye viewing has been advocated for exploring detail-in-context in complicated diagrams [F86, MRC91, SB94, LR94]. As its name suggests, the technique provides a movable virtual magnifying lens. The technique has not yet been popularly accepted for browsing large graphs. One problem is that arbitrary regions of large layouts often may not make much sense locally. Also, it can be difficult to trace edges that cross the edge of the virtual lens. Multiple lenses complicate matters further, and achieving enough performance to support high interactivity can be a challenge, particularly when a nonlinear lens function is chosen. The adjustable level-of-detail approach embodied in Pad/Pad++ [BSH94] is a different kind of attack on this problem, but assumes hierarchically-structured data.

A key point in Furnas' 1986 paper is that a fisheye view is a logical construct not necessarily tied to a fixed geometric display. We advocate dynamic graph layout for logical fisheye viewing of large graphs. Dynamic layout offers a way of automatically adjusting the contents of views in an understandable way, without constraining the placement of objects to a fixed, static layout. In a logical fisheye view, a user initially sets a focus node or set of objects and then incrementally adjusts the visible set, adding new objects of interest and deleting others less interesting, thus navigating through a series of diagrams to explore part of a large network. (Admittedly, such views are not necessarily repeatable: the same place in the graph may look different when reached by different traversals. On the other hand, repeatability has not usually been considered important even for static layout.)

Viewing dynamic data. In many settings, graph diagrams are applied to visualizing dynamic systems. Graph layout movies could be an appropriate way of showing the histories of dynamic graphs. Incremental stability is necessary for such visualizations to reveal what is actually changing in the structure of the underlying data.

Interactive graph editing. Often, user interfaces based on graph diagrams support interactive editing. Good dynamic layout algorithms could improve the usability of these interfaces. Commercial CASE tools often rely on manual node placement and automatic routing of inserted edges by local search. Though perhaps a step in the right direction, this approach seems weak in that the user has all the responsibility for node placement.

An Experimental Testbed

The design of effective dynamic layout heuristics and user interfaces is a fruitful area for research, as there is at present very little experimental experience. Our thesis in creating layout heuristics is that the highest priority be given to keeping layouts consistent with diagram-specific aesthetic rules that help reveal graph structure Subject to this, layouts should be stable so that users can retain a "mental map" of a diagram as it is adjusted [ELMS91]. Perceptual psychology has uncovered a few clues about ways that users may internalize images, such as diagrams [K94]. It seems important to understand more about the connection between vision, cognition, and aspects of layout stability such as