Using constraints to achieve stability in automatic graph layout algorithms

ABSTRACT

Automatic layout algorithms are commonly used when displaying graphs on the screen because they provide a “nice” drawing of the graph without user intervention. There are, however, a couple of disadvantages to automatic layout. Without user intervention, an automatic layout algorithm is only capable of producing an aesthetically pleasing drawing of the graph. User- or application-specified layout constraints (often concerning the semantics of a graph) are difficult or impossible to specify. A second problem is that automatic layout algorithms seldom make use of information in the current layout when calculating the new layout. This can also be frustrating to the user because whenever a new layout is done, the user's orientation in the graph is lost. This paper suggests using 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, the constraints specified by the current layout are used when calculating the new layout to achieve a more stable layout. This approach allows a continuum between manual and automatic layout by allowing the user to specify how stable the graph's layout should be.

REFERENCES

• 1: James F. Allen, Maintaining knowledge about temporal intervals, Communications of the ACM, v.26 n.11, p.832-843, Nov. 1983 [doi>10.1145/182.358434]
• 2: C Batini , E Nardelli , R Tamassia, A Layout algorithm for data flow diagrams, IEEE Transactions on Software Engineering, v.12 n.4, p.538-546, April 1986
• 3: K.-F. BShringer. Stability in graph layout algorithms. Master's thesis, University of Karlsruhe, Institute for Inforrnatics, July 1989. In German.
• 4: E. R. Gansner , S. C. North , K. P. Vo, DAG—a program that draws directed graphs, Software—Practice & Experience, v.18 n.11, p.1047-1062, Nov. 1988 [doi>10.1002/spe.4380181104]
• 5: A. K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8:99-118, 1977.
• 6: Eli Benjamin Messinger , Robert H. Henry, Automatic layout of large directed graphs, 1988
• 7: U. Montanaxi. Networks of constraints: Fundamental properties and applications to picture processing, information Sciences, 7:95-132, 1974.
• 8: F. J. Newbery. EDGE: An extendible directed graph editor. Techniced Report 8/88, University of Karlsruhe, Institute for Informatics, June 1988.
• 9: F.J. Newbery. An interface description language for graph editors. In Proc. of the IEEE 1988 Workshop on Visual Languages, Pittsburgh, PA, October 1988.
• 10: F. Puppe. Introduction to Expert Systems. Springer Verlag, 1988. In German.
• 11: G. Robins. The ISI grapher: a portable tool for displaying graphs pictorially. Computers in Symbolic Graphs and Communications (see. Sven Moer), Helsinki~ Finland, August 17-18 1987. Symboliikka '87. Information Sciences Institute, Marina Del Rey, CA.
• 12: L. A. Row , M. Davis , E. Messinger , C. Meyer , C. Spirakis , A. Tuan, A browser for directed graphs, Software—Practice & Experience, v.17 n.1, p.61-76, Jan. 1987 [doi>10.1002/spe.4380170107]
• 13: K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man, and Cybernetics, SMC-11(2):109- 125, February 1981.
• 14: R. Tamassia , C. Batini , M. Talamo, An algorithm for automatic layout of entity-relationship diagrams, Proc. of the third international conference on Entity-relationship approach to software engineering, p.421-439, December 1983, Anaheim, California, United States
• 15: Roberto Tamassia , Giuseppe Di Battista , Carlo Batini, Automatic graph drawing and readability of diagrams, IEEE Transactions on Systems, Man and Cybernetics, v.18 n.1, p.61-79, January/February 1988 [doi>10.1109/21.87055]
• 16: Walter F. Tichy , Frances J. Newbery, Knowledge-based editors for directed graphs, Proc. of the 1st European Software Engineering Conference on ESEC '87, p.101-109, December 1987, Strasbourg, France

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Interaction techniques

General Terms:
Algorithms, Design, Human Factors