Path: utzoo!attcan!uunet!mcvax!unido!iraun1!Toronto!newbery From: newbery@Toronto.ira.uka.de (Francie Newbery) Newsgroups: comp.graphics Subject: Re: graph drawing algorithm Message-ID: <688@iraun1.ira.uka.de> Date: 14 Nov 88 07:35:50 GMT References: <13391@cisunx.UUCP> <1026@psuhcx.psu.edu> <24313@wlbr.EATON.COM> Sender: news@iraun1.ira.uka.de Reply-To: newbery@Toronto.UUCP (Francie Newbery) Organization: University of Karlsuhe, West-Germany Lines: 169 >I'm looking for an algorithm that takes as input a generalized >graph, determines the space requirements of a display image of the >graph, and finally displays the graph with a minimum of intersecting arcs. >If any one knows of any such algorithm or references please let me know. I have been working on a customizable graph editor as part of my doctoral research at the University of Karlsruhe (West Germany). The implementation is in C++ and X (X11 version will be ready very soon). A customizable graph editor provides a consistent user interface to several applications. Several graph layout algorithms are available to display the graph. The user can group nodes/edges into subgraphs and view them zoomed-in or zoomed-out. For more information, e-mail to newbery@ira.uka.de (but please try to keep it short as e-mail is very expensive for us, both sending and receiving). The following is a partial bibliography of research in this area. EDGE and Related Papers ----------------------- Walter F. Tichy and Frances J. Newbery Knowledge-based Editors for Directed Graphs Proc. of the 1st European Software Engineering Conference (Sept. 9-11 1987) Lecture Notes in Computer Science No. 289, Springer Verlag Howard K. Nichols and Dan Simpson eds. pp. 101--109 Frances J. Newbery EDGE: An Extendible Directed Graph Editor Dept. of Informatics, University of Karlsruhe, 7500 Karlsruhe 1, West Germany Technical Report Number 8/88 June 1988 Frances J. Newbery An Interface Description Language For Graph Editors Proc. of the IEEE 1988 Workshop on Visual Languages (October 10-12, 1988) Pittsburgh, PA Walter F. Tichy and Blake Ward A Knowledge-Based Graphical Editor Dept. of Informatics, University of Karlsruhe, 7500 Karlsruhe 1, West Germany Technical Report Number 3/87 Jan. 1987 Other Graph Editors and Layout Algorithms for Graphs ----------------------------------------------------- Peter Eades and Roberto Tamassia Algorithms for Automatic Graph Drawing: An Annotated Bibliograph University of Quennsland, Dept. of Computer Science, St. Lucia, Queensland, 4067, Australia Report Number 82 July 1987 Carlo Batini and Enrico Nardelli and Roberto Tamassia A Layout Algorithm for Data Flow Diagrams IEEE Transactions on Software Engineering Vol SE-12, Number 4, April 1986 pp. 538-546 Roberto Tamassia and Guuseppe Di Battista and Carlo Batini Automatic Graph Drawing and Readability of Diagrams IEEE Transactions on Systems, Man, and Cybernetics Volume SE-18, Number 1, Jan/Feb 1989, pp61-79 E.R. Gansner, S.C. North, K.P. Vo DAG: A Program that Draws Directed Graphs AT & T Bell Laboratories, Murray Hill NJ 07974 Howard Trickey DRAG: A Graph Drawing System Proceedings of the International Conference on Electronic Publishing, Document Manipulation and Typography Cambridge University Press, April 1988 Marie-Jose Carpano Automatic Display of Hierarchized Graphs for Computer-Aided Decision Analysis IEEE Transactions on Systems, Man, and Cybernetics Volume SMC-10, Number 11, pp 705--715, Nov 1980 Gabriel Robins The ISI Grapher: a Portable Tool for Displaying Graphs Pictorially Symboliikka '87 (August 17-18 1987) Helsinki, Finland (Information Sciences Institute, Marina Del Rey, CA) Lawrence A. Rowe and Michael Davis and Eli Messinger and Carl Meyer and Charles Spirakis and Allen Tuan A Browser for Directed Graphs Software--Practice and Experience, Jan 1987 Volume 17, Number 1, pp. 61--76 Kozo Sugiyama and Shojiro Tagawa and Mitsuhiko Toda Methods for Visual Understanding of Hierarchical System Structures IEEE Transactions on Systems, Man, and Cybernetics Volume SMC-11, Number 2, Feb. 1981, pp. 109--125 Kozo Sugiyama A Readability Requirement in Drawing Digraphs: Level Assignment and Edge Removal for Reducing Total Length of Lines International Institute for Advanced Study of Social Information Science Numazu, Japan Number 45, March 1984 Kozo Sugiyama A Cognitive Approach for Graph Drawing Cybernetics and Systems: An International Journal Number 18, 1987, pp. 447--488 Kozo Sugiyama and Mitsuhiko Toda Structuring Information for Understanding Complex Systems: A Basis for Decision Making FUJITSU Scientific and Technical Journal Volume 21, Number 2, pp. 144--158, June, 1985 Planar Graph Layout ------------------- Chiba, N. and Onoguchi, K. and Nishizeki, T. Drawing Plane Graphs Nicely Acta Informatica Volume 22, pp.187--201, 1985 G. Di Battista and R. Tamassia and E. Nardelli Plane Representations of Acyclic Digraphs Dipartimento Di Informatica E Sistemistica, Universita Degli Studi Di Roma Number 6.87 March 1987 Hopcroft, John and Tarjan, Robert Efficient Planarity Testing Journal of the ACM Volume 21, Number 4, 1974, pp. 549--568 R. J. Lipton and S. C. North and J. S. Sandberg A Method for Drawing Graphs Proceedings of the Symposium on Computational Geometry Baltimore, MD (June 1985) pp. 153--160 Donald R. Woods Drawing Planar Graphs June 1981 PhD Thesis, Dept. of CS, Stanford University Entity Relationship Diagram Layout ---------------------------------- R. Tamassia and C. Batini and M. Talamo An algorithm for automatic layout of entity relationship diagrams Entity-Relationship Approach to Software Engineering C.G. Davis and S. Jajodia and P.A. Ng and R.T. Yeh eds North-Holland Publishing Co. 1983 pp. 421--439 Tree Layout Algorithms ---------------------- Joseph Manning and Mikhail J. Atallah Fast Detection and Display of Symmetry in Trees Dept of Computer Science, Purdue University Technical Report Number 606, 1986 C. Wetherell and A. Shannon Tidy Drawings of Trees IEEE Transactions on Software Engineering Volume 5, Number 5, Sept. 1979, pp. 514--520 Edward M. Reingold and John S. Tilford Tidier Drawings of Trees IEEE Transactions on Software Engineering Volume 7, Number 2, March 1981, pp. 223--228 The Complexity of Drawing Trees Nicely Kenneth J. Supowit and Edward M. Reingold Acta Informatica Volume 18, 1983, pp. 377--392 J. G. Vaucher Pretty Printing of Trees Software--Practice and Experience Volume 10, 1980, pp. 553--561