Constraint-Based Spring-Model Algorithm for Graph Layout

Kamps, Thomas and Kleinz, Joerg and Read, John (1996) Constraint-Based Spring-Model Algorithm for Graph Layout. In: Symposium on Graph Drawing, GD 1995, September 20-22, 1995, Passau, Germany , pp. 349-360 (Official URL: http://dx.doi.org/10.1007/BFb0021818).

Full text not available from this repository.

Abstract

In this paper we will discuss the question of how to develop an algorithm for automatically designing an optimal layout of a given constraint graph. This automatic layout algorithm must observe certain aesthetic principles, which facilitate the user's interpretation of the graph. The constraint graph is generated by the visualization algorithm AVE (Automatic Visualization Engine) which decides in this case that the object relation between the objects which are to be graphically represented must be visually realized by lines. The constraints describe how subsets of objects are geometrically represented relative to each other. We require that each individual object be of fixed size throughout the algorithm, but we allow for each of these sizes to differ one from another. This automatic layout algorithm is developed along the lines of a (spring) force model, a method which has its roots in such works as [Eade]. As a measure of any particular layout's fidelity to our aesthetic principles, we have developed a function which assigns a real value to each possible layout. We have insured that this function has good differentiability properties, in order that we may exploit gradient descent methods to arrive at a layout that minimizes this function. Any such layout is then by definition the optimal layout we seek. These gradient methods are integral in assuring that the algorithm we develop can efficiently implement the aesthetic principles so that we obtain a very fast routine.

Item Type:Conference Paper
Additional Information:10.1007/BFb0021818
Classifications:M Methods > M.300 Dynamic / Incremental / Online
M Methods > M.400 Force-directed / Energy-based
G Algorithms and Complexity > G.560 Geometry
ID Code:177

Repository Staff Only: item control page

References

Davidson R. Harel D., Drawing Graphs Nicely Using Simulated Annealing. Technical Report CS89-13, Department of Applied Mathematics and Computer Sciences, Weizman Institute of Sciences, Israel, July, 1989.

Di Battista G. Eades P. Tamassia R. Tollis G., Algorithms for Drawing Graphs: an Annotated Bibliography, Brown University, Department of Computer Science, Technical Report, 1993.

Dengler E. Friedell M. Marks J., Constraint-Driven Diagram Layout, Proceedings of the IEEE Symposium on Visual Languages, 1993.

Eades P., A Heuristic Graph Drawing, Congressus Numerantium, 42, 1984.

Fischer D. H. Rostek L., SFK: A Smalltalk Frame Kit, Concepts and Use, To appear as GMD Report.

Frick A. Ludwig A. Mehldau H., A fast Adaptive Layout Algorithm for Undirected Graphs (Extended Abstract and System Demonstration, in Graph Drawing, DIMACS International Workshop, GD '94, Princeton New Jersey, October 1994, Lecture Notes in Computer Science, Springer Verlag

Fruchterman T. Reingold E., Graph Drawing by Force-Directed Placement. In Software Practice and Experience, 21(11), November 1991.

Golovchinsky G. Kamps T. Reichenberger K., Subverting Structure: Data-driven Diagram Layout, accepted at IEEE Visualization '95, Atlanta, October 30-November 1 1995.

Kamps T. Reichenberger K. (1994a), Automatic Layout as an Organization Process, GMD Report, No. 825, Sankt Augustin 1994.

Kamps T. Reichenberger K. (1994b), Automatic Layout Based on Formal Semantics, in Catarci, T. et. al. (Eds.), Proceedings of the Workshop of Advanced Visual Interfaces, AVI '94, June 1194, Bari, Italy

Kamada T. Kawai S., An Algorithm for General Undirected Graphs, in Information Processing Letters 31 (1989). Elsevier Science Publishers B. V. (North Holland).

Kosak C. Marks J. Shieber S., Automating the Layout of Network Diagrams with Specified Visual Organization, in IEEE Transactions On Systems. MAn and Cybernetics, Vol 24, No. 3, March 1994.

Kleinz J., Entwicklung eines constraint-gesteuerten 2D-Positionierungsverfahrens, to appear as GMD report.

Lin T. Eades P., Integration of Declarative and Algorithmic Approaches for Layout Creation, in Proceedings of DIMACS International Workshop, GD '94 Princeton, New Jersey, USA, October 1994, Tamassia R. Tollis G. (Eds.), Lecture Notes in Computer Science 894, 1994.

Mackinlay J. (1986) Automating the Design of Graphical Presentations of Relational Information, in ACM Transactions on Graphics, 5(2).

Reichenberger K. Kamps T. Golovchinsky G., Towards a Generative Theory of Diagram Design, accepted at IEEE Symposium on Information Visualization (Infovis '95), Atlanta, October 31 1995.

Roth S. F. Hefley W. E. Intelligent Multimedia Presentation Systems: Research and Principles, in Mark Marbury (Ed.) Intelligent Multi-Media Interfaces, AAAI Press, 1993.

Sugiyama K. Misue K. A Simple and Unified Method for Drawing Graphs: Magnetic-Spring Algorithm, in Proceedings of DIMACS International Workshop, GD '94 Princeton, New Jersey, USA, October 1994, Tamassia R. Tollis G. (Eds.), Lecture Notes in Computer Science 894, 1994.