ayers@srcsip.UUCP (timingila) (09/09/88)
Could someone please point me to an algorithm for drawing a graph, given a root node to begin from? I would like the display to be as uncluttered as possible. For example, if two paths converge into one I would like to ensure that those two paths are drawn beside one another. And I would like neat even spacing. I've come up with routines to draw non-converging graphs (trees) and graphs that converge to one node, but I don't know how efficient they are compared to other algorithms. And I thought before I put too much effort into this "any random graph" business, I would ask you folks. Thanks a lot, tim
lmiller@venera.isi.edu (Larry Miller) (09/11/88)
In article <8362@srcsip.UUCP> ayers@srcsip.UUCP (timingila) writes: >Could someone please point me to an algorithm for drawing a graph, and goes on to ask about one that is aesthetic, with certain properties. ISI, part of the computer science department at USC, has available a LISP-pased "grapher." Gabe Robins is the person responsible for implementing, and also developing, the algorithms, and has done a superb job. It is written in Common Lisp, and currently runs on HPs, Lisp machines, TI Explorers, etc. The graphics calls for the HP version are X, so it is really quite portable. Contact: Gabe Robins USC/ISI 4676 Admiralty Way Marina del Rey, CA. 90292 213-822-1511 arpa-net: robins@vaxab.isi.edu (no uucp) There is a license agreement that has to be signed, and there is a very small charge to cover distribution of the tape, etc. Larry Miller lmiller@venera.isi.edu (no uucp) USC/ISI 213-822-1511 4676 Admiralty Way Marina del Rey, CA. 90292
north@ulysses.homer.nj.att.com (Steve North[arm]) (09/12/88)
A common approach for drawing directed graphs is to rank the nodes, then find good positions within ranks. Here is a good place to start reading: K. Sugiyama, K., S. Tagawa and M. Toda, "Methods for Visual Understanding of Hierarchical System Structures", IEEE Transactions on Systems, Man, and Cybernetics, SMC-11, No. 2, 1981, pp. 109--125. Many people have been working in this area. You might want to look up some of the papers by Peter Eades, Larry Rowe, or M. Carpano. Peter Eades recently has been compiling a bibliography of graph-drawing algorithms, probably available as a tech report from the Dept. of Computer Science, University of Queensland, St. Lucia, Queensland 4067, Australia. Emden Gansner, Phong Vo, and I have improved the basic Sugiyama heuristic to get significantly better drawings in less time. This work is described in a tech report which you can get by writing to Stephen C North, Room 3C-539, AT&T Bell Laboratories, 600 Mountain Ave., Murray Hill, NJ 07974; or by sending electronic mail to north%ulysses@research.att.com Stephen C. North
radack@daffy.CES.CWRU.Edu (Gerald Radack) (09/21/88)
In article <6265@venera.isi.edu> lmiller@venera.isi.edu.UUCP (Larry Miller) writes: >ISI, part of the computer science department at USC, has available >a LISP-pased "grapher." .... >There is a license agreement that has to be signed, and there is a very >small charge to cover distribution of the tape, etc. I don't consider $450 a "very small charge."