Constrained Graph Layout

He, Weiqing and Marriott, Kim (1997) Constrained Graph Layout. In: Symposium on Graph Drawing, GD '96, September 18-20, 1996, Berkeley, California, USA , pp. 217-232 (Official URL:

Full text not available from this repository.


Most current graph layout technology does not lend itself to interactive applications such as animation or advanced user interfaces. We introduce the constrained graph layout model which is better suited for interactive applications. In this model, input to the layout module includes suggested positions for nodes and constraints over the node positions in the graph to be layed out. We describe three implementaions of layout modules which are based on the constrained graph layout model. The first two implementations are for undirected graph layout and the third is for tree layout. The implementations use active set techniques to solve the layout. Our empirical evaluation shows that they are quite fast and give reasonable layout.

Item Type:Conference Paper
Additional Information:10.1007/3-540-62495-3_50
Classifications:M Methods > M.300 Dynamic / Incremental / Online
M Methods > M.200 Animation
ID Code:130

Repository Staff Only: item control page


G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Algorithms for drawing graphs: An annotated bibliography. Comput. Geom. Theory Appl., 4: 235-282, 1994.

A. Borning. The programming languages aspects of ThingLab, a constraint-oriented simulation laboratory. ACM Transactions on Programming Languages and Systems, 3(4):252-387, 1981.

M.J. Box, D. Davies, and W.H. Swann. Non-linear optimization techniques. Oliver&Boyd, 1969.

F.J. Brandenburg. Designing graph drawings by layout graph grammars. In Roberto Tamassia and Ioannis Tollis, editors, Proceedings of Graph Drawing '94, volume 894 of LNCS, pages 416-427. DIMACS Workshop on GD, Springer-Verlag, 1995.

F.J. Brandenburg, M. Himsolt, and C. Rohrer. An experimental comparison of force-directed and randomized graph drawing algorithms. In F.J. Brandenburg, editor, Graph Drawing (Proc. GD '95), volume 1027 of LNCS, pages 76-87. Springer-Verlag, 1996.

S.S. Chok and K. Marriott. Automatic construction of user interfaces from constraint multiset grammars. In IEEE Symposium on Visual Languages, 1995.

I.F. Cruz and A. Garg. Drawing graphs by example efficiently: trees and planar acyclic digraphs. In Roberto Tamassia and Ioannis Tollis, editors, Proceedings of Graph Drawing '94, volume 894 of LNCS. DIMACS Workshop on GD '94, Springer-Verlag, 1995.

R. Davidson and D. Harel. Drawing graphs nicely using simmulated annealing. Technical report, Dept. of Appl. Math. and Comp. Sci., 1991.

E. Dengler, M. Friedell, and J. Marks. Constraint-driven diagram layout. In Proc. of the 1993 IEEE Workshop on Visual Languages, pages 330-335, 1993.

P. Eades. A heuristic for graph drawing. Congressus Numerantium, 42:149-160, 1984.

P. Eades, W. Lai, K. Misue, and K. Sugiyama. Preserving the Mental Map of a Diagram. In Proc. Compugraphics `91, pages 24-33, 1991.

P. Eades and J. Marks. Graph-drawing contest report. In Symposium on Graph Drawing, GD '95, LNCS 1027, Passau, Germany, September 1995, Springer.

R. Fletcher. Practical Methods of Optimizations. John Wiley & Sons, 1987.

A. Frick, A. Ludwig, and H. Mehldau. A fast adaptive layout algorithm for undirected graphs. In Proceedings of DIMACS International Workshop on GD '94, LNCS 894, Princeton, New Jersey, USA, October 1994. Springer-Verlag.

T.M.J. Fruchtermann and E.M. Reingold. Graph drawing by force-directed placement. Software Practice and Experience, 21(11):1129-1164, November 1991.

A. Garg, M.T. Goodrich, and R. Tamassia. Area-efficient upward tree drawing. In Proceedings of the 9th Annual Symposium on Computational Geometry, ACM, 1994.

D. Goldfarb and A. Idnani. A numerically stable dual method for solving strictly quadratic programs. Math. Prog., 27:1-33, 1983.

R. Helm and K. Mariott. Declarative Graphics. In Proc. of the 3rd International Conference on Logic Programming, LNCS 225, pages 513-527, London, England, 1986. Springer-Verlag.

R. Helm and K. Mariott. A declarative specification and semantics for visual languages. J. of Visual Lang. and Comp., 2:311-331, 1991.

R. Helm, K. Mariott, T. Huynh, and J. Vlissides. An object-oriented architecture for constraint-based graphical editing. In Object-Oriented Programming for Graphics, pages 217-238. Springer-Verlag, 1995.

J.Q. Walker II. A node-position algorithm for general tree. Software Practice and Experience, 20(7):685-705, July 1990.

T. Kamada. Visualizing abstract objects and relations: a constraints-based approach, vol. 5 of Computer Science. Singapore, New Jersey: World Scientific, 1989.

T. Kamada and S. Kawai. An algorithm for drawing general undirected graphs. Information Processing Letters, 31(1):7-15, April 1989.

T. Kamps, J. Kleinz, and J. Read. Constraint-based spring-model algorithm for graph layout. In Symp. on Graph Drawing, GD '95, LNCS 1027, Passau, Germany, September 1995. Springer-Verlag.

P. Kikusts and P. Rucevskis. Layout algorithm of graph-like diagrams for grade windows graphic editors. In Symp. on Graph Drawing, GD '95, LNCS 1027, Passau, Germany, September 1995. Springer-Verlag.

T. Lin and P. Eades. Integration of declarative and algorithmic approaches for layout creation. Technical Report TR-HJ-94-10, CSIRO Division of Information Technology, Centrefor Spatial Information Systems, 1994.

P. Luders, R. Ernst, and S. Stille. An approach to automatic display layout using combinatorial optimization. Software Practice and Experience, 25(11):1183-1202, 1995.

K. Misue, P. Eades, W. Lai, and K. Sugiyama. Layout Adjustment and the Mental Map. J. of Visual Languages and Computing, pages 183-210, June 1995.

B.A. Myers, D.A. Giuse, R.B. Dannenberg, B.V. Zanden, D.S. Kosbie, E. Pervin, A. Mickish, and P. Marchal. Garnet: comprehensive support for graphical highly interactive user interfaces. Computer, pages 71-85, November 1990.

S.C. North. Incremental layout in dynadag. In Symp. on Graph Drawing, GD '95, LNCS 1027, Passau, Germany, September 1995. Springer-Verlag.

T. Lin, P. Eades, and X. Lin. Two tree drawing conventions. Technical Report 174, Key Centre for Software technology, Department of Computer Science, The University of Queensland, 1990.

F.N. Paulisch. The design of an extendible graph editor. LNCS 704, Springer-Verlag 1993.

E.M. Reingold and J.S: Tilford. Tidier drawing of trees. IEEE Trans. on Softawre Engineering, SE-7(2):223-228, March 1981.

K. Sugiyama and K. Misue. A simple and unified method for drawing graphs: magnetic-spring algorithm. In Proceedings of DIMACS International Workshop on GD '94, LNCS 894, Princeton, New Jersey, USA, October 1994. Springer-Verlag.

K. Tsuchida, Y. Adachi, Y. Oi, Y. Miyadera, and T. Yaku. Constraints and algorithm for drawing tree-structed diagrams. In Proc. of the Inter. Workshop on Constraints for Graphics and Visualization, CGV '95, Cassis, France, September 1995.

D. Tunkelang. A practical approach to drawing undirected graphs. Carnegi Mellon University, 1994.

J.G. Vaucher. Pretty-printing of trees. Software Practice and Experience, 10:553-561, 1980.

Weitzman, Louis, and Wittenburg, Kent. (1993) Relational Grammars for Interactive Design. In Proc. IEEE Symp. on Visual Lang., August 24-27, Bergen, Norway, pages 4-11.

C. Werthell and A. Shannon. Tidy drawing of trees. IEEE Trans. on Softawre Engineering, SE-5(5):514-520, September 1979.