interactively, or automatically by the system, yielding incremental graph updates. { VPM displays distributed programs as graphs [4]. Processes and resources are drawn as nodes. Edges represent dependence and communication. Subgraphs (that is, zones [10] or clusters [16]) show distribution across hosts. VPM would benefit greatly from stable incremental graph layout. Furthermore, graph updates are issued at an exceptionally high rate (the rate of system call issue) so efficiency is critical.

Most graph drawing algorithms to date are not incrementally stable. They usually apply batch techniques to optimize objectives such as reducing total edge crossings or edge length. A small change in the input set, even just its ordering, may yield unpredictable, instable changes between successive layouts. This may occur even if a previous layout is taken as a starting configuration. The results can be confusing when viewing a sequence of layouts. An example is shown in fig. 1 made by an extension of the algorithm of Sugiyama et al [20]. Graphs (a) and (b) differ by only one edge. Although the drawing could be updated by moving a subgraph downward, as shown in (c), the layout system makes more drastic, unnecessary changes.

Most of our applications involve software engineering diagrams drawn hierarchically, so our immediate goal is to incrementalize" our variant of Sugiyama's hierarchical drawing algorithm. Some similar issues, though, are encountered in making other kinds of layouts incrementally.

2 Previous Work

Significant progress has been made in drawing dynamic trees [15] (using subtree contours), planar graphs [2] and series-parallel graphs [7]. Although these are useful techniques for these restricted classes of graphs, they are not directly applicable to general graph drawing.

Hornick, Miriyala and Tamassia describe a practical incremental edge router for orthogonal drawings, such as entity-relation diagrams [14]. Nodes are placed externally (typically, by the user); the system routes edges incrementally by a shortestpath technique that accounts for edge length, crossings, and number of bends. The technique would have to be extended to handle automatic node placement and adjusting layouts to make space for new objects.

Lyons describes a way of incrementally improving layouts of undirected graphs such as those made by force directed modeling with unconstrained optimization [13]. The idea is to adjust regions where nodes are too close by computing Voronoi sets around each node and moving each node that has a conflict to a better place within its region. Because each node moves to a point that is closer to its old position than to any other node, faces are preserved. This technique is claimed to give better and more stable results than alternatives, such as re-solving a spring model with adjustments in springs intended both to force overlapping nodes apart, and to anchor nodes to their original positions. Lyons' algorithm is effective for this problem, but does not address how to maintain stability if the underlying graphs change. Also, virtual physical modeling is somewhat limited by the characteristic that all edges tend toward unit length.