sbj@psuhcx.psu.edu (Sanjay B. Joshi) (11/03/88)
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. Thanks sanjay.
mh@wlbr.EATON.COM (Mike Hoegeman) (11/07/88)
In article <1026@psuhcx.psu.edu> sbj@psuhcx (Sanjay B. Joshi) writes: >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. > >Thanks >sanjay. I'm quite interested in this too. If anyone out there has some info please post it instead of replying. thanks
mschedlb@hawk.ulowell.edu (Martin Schedlbauer) (11/08/88)
In article <24313@wlbr.EATON.COM> mh@wlbr.eaton.com.UUCP (Mike Hoegeman) writes: >In article <1026@psuhcx.psu.edu> sbj@psuhcx (Sanjay B. Joshi) writes: > >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. > > > >Thanks > >sanjay. > >I'm quite interested in this too. If anyone out there has some info >please post it instead of replying. thanks > I probably won't be of too much help right now, but I'll check my sources as soon as get them back. Anyway, I think there is some interesting stuff on that subject (in terms of references) in the Proceedings for the 1988 IEEE International Workshop on Visual Languages held October 10-12 in Pitts- burgh, PA (hosted by University of Pittsburgh.). A paper by Frances Newbery presented at the conference was concerned with that subject. Maybe that'll help some. As I said I'll try to get my proceedings back and post more exact references. From what I remember , there are several 'standard' algorithms for displaying graphs and minimizing arc crossings. She implemented some as part of her doctoral work at the University of Karlsruhe, Germany. ...Martin ============================================================================== Martin J. Schedlbauer Dept. of Computer Science University of Lowell Lowell, MA 01854
mike@pbinfo.UUCP (Michael Utermoehle) (11/09/88)
In article <10091@swan.ulowell.edu> mschedlb@hawk.ulowell.edu (Martin Schedlbauer) writes: >In article <24313@wlbr.EATON.COM> mh@wlbr.eaton.com.UUCP (Mike Hoegeman) writes: >>In article <1026@psuhcx.psu.edu> sbj@psuhcx (Sanjay B. Joshi) writes: >> >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 probably won't be of too much help right now, but I'll check my sources >as soon as get them back. Anyway, I think there is some interesting stuff >on that subject (in terms of references) in the Proceedings for the 1988 >IEEE International Workshop on Visual Languages held October 10-12 in Pitts- >burgh, PA (hosted by University of Pittsburgh.). A paper by Frances Newbery >presented at the conference was concerned with that subject. Maybe that'll >help some. > EDGE - an extendible directed graph editor is developed (by Frances Newbery newbery@ira.uka.de) at the Uni. of Karlsruhe. It is written in C++ and uses the X Window Sytstem (cur. X10). EDGE is available on Sun workstations, MicroVaxen and IBM RTs. The graph editor consists of a display engine, a set of layout specs, a user interface and a default editor. There are cur. four automatic layout algorithm available: One for min. edge crossing (Sugiyama), cycles in a graph, tree-like layout in linear time and Reingold/Tilford algorithm. There are several demo programs available: A Project Management Editor, A Program Animator (very simple), Directory Browser, Logic Simulator (very simple) and Petri Net Editor. Some nice features: Applications are very easy to interface (If you adopt the data structure). Multilevel graphical abstruction - subgraphs with zoom-in and zoom-out. Two papers are available: 1. EDGE: An Extendible Directed Graph Editor 2. An interface description language for graph editors (the paper from IEEE 1988 VL-workshop) University of Karlsruhe, Postfach 6980, D-7500 Karlsruhe, W-Germany There is another graph editor developed at the University of Paderborn: PLEXUS - A system for implementing Hierarchical Graph Algorithmus by Egon Wanke and Prof. Dr. Thomas Lengauer PhD Such algorithms process hierarchical defined graphs or cellular graph grammars. PLEXUS supports the implementation of hierar- chical graph algorithms based on the bottom-up method by providing the necessary basic data structures and functions. The system is organized in several layers for implementation of the basic data-types set,list and object, implementation of the necessary graph concepts and routines for hierchical and non-hierachical graph processing and editing routines. A graph editor has been implemented that allows the mani- pulation of graphs on the screen. Most of the implementation algorithms can be called from within the editor. New algorithms or commands can easily be integrated into the editor. During the interactive generation of new vertices and nonterminals the editor assigns to each new object screen coordinates. Several commands within the editor can change these screen coordinates and thus modify the image of the graph on the screen. Other commands execute procedures that generate expansions of hierarchical graphs and draw the result on the screen or store it into files (if the expansion does not fit into memory). The system has been implemented in the programming language C on a Sun-3 Workstation. All graphic routines are based on the SunView system. Currently the non-hierarchical features of the system are used as the basis for developing software for integrated circuit layout. (E.Wanke is reachable under ..!uunet!unido!pbinfo!egon) Greetings mike
newbery@Toronto.ira.uka.de (Francie Newbery) (11/14/88)
>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