CONTINUE?

Expanding the text here will generate a large amount of data for your browser to display

Incremental Layout in DynaDAG

Stephen C. North
north@research.att.com

Software and Systems Research Center
AT&T Bell Laboratories
Murray Hill, N.J. 07974 U.S.A.

Abstract. Generating incrementally stable layouts is important for visualizing dynamic graphs in many applications. This paper describes DynaDAG, a new heuristic for incremental layout of directed acyclic graphs drawn as hierarchies, and its application in the DynaGraph system.

1 Introduction

Effective techniques have been developed for some important families of graph layouts, such as hierarchies, planar embeddings, orthogonal grids and forced-directed (spring) models [1]. These techniques have been incorporated in practical user interfaces that display static diagrams of relationships between objects [19, 18, 17]. Static diagrams are not completely satisfactory because in many situations, the displayed graphs can change. Three common scenarios are:

Manual editing. Most interactive graph drawing systems allow users to manually insert and delete nodes and edges. Layouts must be updated dynamically to reflect such changes.

Browsing large graphs. When only static layout is available, browsing large graphs usually means drawing the entire graph and then viewing portions in a window with pan and zoom controls, fisheye lenses, etc. The problem is that the section in the current window may not be very informative. For example it may contain edge segments whose endpoint nodes are outside the window, or nodes whose placement can be rationalized globally but not locally. Incremental layout offers the alternative of directly adjusting the set of displayed objects to make informative displays.

Visualizing dynamic graphs. Often, data being visualized is subject to change. In our experience with the dotty system, we found many applications for graph animations:

{ CIAO is a program database that displays dependencies between the types, data, functions and files in a C or C++ program [6]. Programs change throughout their life-cycle as they are debugged, maintained, and improved, so graph views should reflect such changes.
{ Improvise is a multimedia viewer for software process models [11]. These models are incrementally corrected and refined. Users report that stable incremental layout and manual editing of diagrams are essential.
{ LDBX is a prototype graphical debugger that runs on an unmodified dbx textbased debugger [17]. It displays data structure graphs. Records are drawn as nested boxes containing primitive data or pointer fields. Pointers may be traced