Stability in Automatic Graph Layout Algorithms

Joint work with Frances Newbery Paulisch and Walter F. Tichy.

Automatic layout algorithms are commonly used when displaying graphs because they provide a ``nice'' drawing of the graph without user intervention. There are, however, several disadvantages to automatic layout. User- or application-specific layout constraints are usually not taken into account. A second problem is that automatic layout algorithms seldom make use of information in the current layout for the next incremental update. This can be frustrating to the user because whenever a new layout is done, the user's orientation in the graph is lost.

We propose layout constraints to solve both of these problems. We show how user-specified layout constraints may be easily added to many automatic graph layout algorithms. Additionally, layout information of the current graph generates constraints that are taken into account after the graph has been changed. This approach provides a continuum between manual and automatic layout by allowing the user to specify how stable the graph's layout should be.


Publications:

  1. K.-F. Böhringer and F. Newbery Paulisch, Using Constraints to Achieve Stability in Automatic Graph Layout Algorithms. Proceedings of the ACM SIGCHI Conference on Human Factors in Computing Systems, Seattle, WA (April, 1990).
  2. K.-F. Böhringer, Stabilität von Algorithmen für Graphenumbruch. Diplom thesis, Department of Computer Science, University of Karlsruhe, Germany (July, 1989).

    Also of interest:

  3. Frances Newbery Paulisch, The Design of an Extendible Graph Editor, Lecture Notes in Computer Science 704, Springer Verlag, Berlin / Heidelberg (1993).


karl@cs.cornell.edu