lws@capybara.comm.wang.com (Lyle Seaman ) (05/10/91)
Here is the info I received in response to my recent query regarding algorithms and/or source for drawing directed acyclic graphs. It turns out my graph is cyclic :-( but I think that xgrab will work anyway :-) if I ever successfully get it built on Risc/OS :-(. ============================= the DAG program (see Nov 1988 SPE) is licensed externally by AT&T in binary form, i think for $500. a university can get a license for free (so far). Stephen North north@ulysses.att.com From: Louis Laborelli <laborell@mimosa.unice.fr> Subject: Re: drawing Directed Acyclic Graphs (algorithm or source) I am happy to work with xgrab , under Interviews . You can easyly modify the code to suit your needs .( We have done that ! ) one problem : tbe garbage collector is not working on my machine . I have had to patch the code to remove the main sources of memory losses . There is also a more ambitious product , from a german university : edge . I have no deep experience with it . We are happy to announce the availability of 'xgrab' (X graph browser) a graph layout and browser package running under X11.R4. Xgrab reads a textual specification of a graph, lays out the graph using heuristics to minimize the number of edge crossings, and displays the graph as labeled nodes and edges in an X window. The user can then edit the graph. Once happy with the graph layout, xgrab can write a postscript file or a text file describing the resulting graph. Xgrab has been used to layout finite state machines, program dependence graphs, pert charts, trees, and much more. It works well for graphs with fewer than 30 nodes, but will work "adequately" for graphs with many more nodes. Xgrab is distributed using standard conventions for anonymous binary ftp of the compressed tar file 'pub/xgrab.tar.Z' from the machine 'cs.washington.edu'. If you take a copy of xgrab, please send mail to 'xgrab@cs.washington.edu' acknowledging that you have taken the software. THERE IS NO SUPPORT. In order to make xgrab run, you will also need version 2.6 of Mark Linton's Interviews software. If you do not already have this software you will need to use anonymous binary ftp of the compressed tar file '2.6.tar.Z' from the machine 'interviews.stanford.edu', and follow the directions contained therein. In addition, you will also need the latest release of the GNU C++ compiler "g++". If you do not already have this, you should grab the compressed tar file '2.6-and-g++.tar.Z' from 'interviews.stanford.edu'. It is unlikely that xgrab will work with AT&T CC. The xgrab software comes with a general purpose garbage collecting storage allocator written by Hans Boehm at Rice [Boehm et al 1988]. Xgrab has been compiled and successfully executed on vax/ultrix, running X11.R4. It was developed under sun/3, and should continue to run fine on that platform. Other platforms have not been tested, but the belief is that the software can port to other platforms that have g++, interviews and X11.R4. If g++ and interviews are not already installed at your site, then it will take a UNIX whiz about 1 day to read the documentation supplied with that software, figure out how to configure and then build the required software. The garbage collector will not run under decstation/ultrix because it has not yet been ported to that platform. In that event, xgrab can be compiled so that it does not recycle any storage. The layout algorithms used in xgrab were derived from algorithms by Sugiyama et al in 1981 [Sugiyama et al 1981]. The basis for the xgrab implementation was originally done by Rowe, Davis, Messinger, Meyer, Spirakis and Tuan [Rowe et al 1987] at the University of California, Berkeley, in a graph browser called 'sungrab' running under SunView. This code was then modified by Greg Barnes while employed as a summer intern at Tera Computer, Seattle, WA. Gregory S. Barnes, greg@cs.washington.edu Robert R. Henry, rrh@cs.washington.edu Computer Science and Engineering Department, FR-35 University of Washington Seattle, WA 98195 USA 206 685 1934 Louis Laborelli Universite de Nice Sophia Antipolis / phone: (33) 92 94 26 89 I3S LISAN - CNRS Batiment 4 \ telex: GRP 970006F 250 rue Albert Einstein / fax: (33) 92 94 28 98 Sophia Antipolis \ e-mail:laborell@zig.inria.fr 06560 Valbonne FRANCE / or laborell@mimosa.unice.fr Date: 29 Aug 90 01:39:16 GMT Reply-To: rt@cs.brown.edu (Roberto Tamassia) Organization: Brown University Department of Computer Science A bibliography on graph drawing algorithms, by Peter Eades and myself, is currently available as a technical report, and will eventually appear in a journal: %A P. Eades %A R. Tamassia %T Algorithms for Automatic Graph Drawing: An Annotated Bibliography %R Technical Report CS-89-09 %I Dept. of Computer Science, Brown Univ. %D October 1989 It lists about 180 papers, both theoretical and application oriented. A monograph on the subject, by the same authors, is under preparation. Roberto Tamassia Department of Computer Science Brown University Providence, RI 02912-1910 >From: hmueller@wfsc4.tamu.edu (Hal Mueller) Newsgroups: comp.theory,comp.graphics Subject: Re: Planar graph embedding Organization: Dept. of Wildlife and Fisheries Sciences, Texas A&M University In article <1990Aug28.210258.29695@cs.umn.edu> martin@cs.umn.edu (Johnny Martin) writes: >A couple of years ago I was given a copy of a paper by Peter Eades and >Roberto Tamassia: "Algorithms for Automatic Graph Drawing: An >Annotated Bibliography." On the bottom of the paper someone scribbled >"to appear July 1987." I don't know where, when, or if it appeared. >In lieu of a more exact reference, I can mail you a copy of the paper. >Send me you postal address, or better yet, if you find out where it >appeared let me know. > This is probably not your paper, but I have a cite for P. Eades, I. Fogg, and D. Kelly: "SPREMB: A System for Developing Graph Algorithms". Technical Report, Dept. Of Computer Science, U. of Queensland, St. Lucia, Queensland, Australia, 1988. -- Hal Mueller Surf Hormuz. hmueller@cs.tamu.edu n270ca@tamunix.Bitnet >From: martin@cs.umn.edu (Johnny Martin) Newsgroups: comp.theory,comp.graphics Subject: Re: Planar graph embedding In article <1990Aug28.155431.12306@Neon.Stanford.EDU> rivin@Gang-of-Four.Stanford.EDU (Igor Rivin) writes: > >Would anyone happen to have a program that would construct a planar >embedding of a planar graph? It needn't check for planarity, though it >might as well. Getting greedy, what about "nice" embeddings, which can >be defined as > >a) ones that look nice > >b) Less fuzzy, but not obviously equivalent to a), ones that attempt >to maximize the smallest angle between the edges, and also minimize >the ratio between the longest and the shortest edge. (I am not sure >this is the best definition, any other ideas?) > > Thanks. > >-- >Igor Rivin Wolfram Research, Inc. >rivin@Gang-of-Four.Stanford.EDU or >rivin@wri.com A couple of years ago I was given a copy of a paper by Peter Eades and Roberto Tamassia: "Algorithms for Automatic Graph Drawing: An Annotated Bibliography." On the bottom of the paper someone scribbled "to appear July 1987." I don't know where, when, or if it appeared. In lieu of a more exact reference, I can mail you a copy of the paper. Send me you postal address, or better yet, if you find out where it appeared let me know. -- johnny martin -- Johnny Martin (martin@umn-cs.cs.umn.edu) Dept. Comp. Sci., 4-192 EE/CS, University of Minnesota, Minneapolis MN 55455 Date: Wed, 8 May 91 09:55:40 EDT From: Bill Hahn <bhahn@bogus.sw.stratus.com> Subject: drawing Directed Acyclic Graphs (algorithm or source) Here it is. I've never send mail to the EMAIL addresses mentioned herein, and they may well be out of date. -bh -------------------------------8<--------------------------------- Article: 1023 of comp.theory Path: lectroid!transfer!crackers!samsung!uunet!decwrl!shelby!neon!news >From: rivin@Gang-of-Four.Stanford.EDU (Igor Rivin) Newsgroups: comp.theory Subject: Planar Graph Layout (Summary) Message-ID: <1990Sep7.171613.4193@Neon.Stanford.EDU> Date: 7 Sep 90 17:16:13 GMT Sender: news@Neon.Stanford.EDU Organization: Computer Science Department, Stanford University Lines: 273 Here is the promised summary of responses so far. Thanks to all who responded. Mike Hutton (mdhutton@theory.toronto.edu) supplied some very interesting comments and a bibliography of work on directed graphs. Here are his comments (the bibliography is at the end of this posting). The ideas you stated for good representations of graphs have been looked at. Unfortunately, the algorithms to display such things are invariably NP-hard (these two are definitely, as are minimum crossings, minimum area, angle ratios, ...) I think that some are provably exponential too. For a survey of graph drawing, you could send mail to Roberta Tamassia, rt@cs.brown.edu. He and Peter Eades have an ongoing bibiliography of current research. Planar drawing is easier than general drawing -- no problems with crossing, and much more restricted structure. Drawing planar graphs with no symmetry requirements (as you mentioned) is linear time -- see Chiba and Nishizeki's paper or book. They have also studied convex drawings, and have a linear algorithm; see also Thomassen's papers for the background graph theory. My thesis involved drawing planar directed graphs, but it concentrates on the testing for whether a graph can be drawn planar, and at the same time having all edges monotonic in the y-direction (`upward'). I have included a copy of my bibliography. In particular, you could look at Nishiziki and Chiba's book, of the DeFrassiux Pach and Pollack paper. I haven't been able to get at the Chrobak paper, but it claims a linear implementation of DeFrassiux et.al.'s algorithm for drawing straight line graphs in a small rectangular grid. For specfic applications, more is known. Specifically, some of the results are polynomial. Drawing Hierarchical graphs (like subroutine charts) is linear time -- this was presented at the Canadian Computational Geometry Conference 2 weeks ago -- I can give you the email address of the authors if you like, but I don't have it handy. There is also a PhD thesis from Stanford in the mid eighties, but I can't remember the name. Can find it if you like, I just don't have it here. Was on graph drawing in general. There is a nice paper by Eades on drawing graphs using 'springs' as the edges and iterating to stabilization which worked well in practice. Roberto Tomassia (rt@cs.brown.edu) has developed (in cooperation with the University of Rome) tools for graph layout, and mentiones work by a student (unnamed) at Brown that indicates that you can do pretty good embedding (low variance in edge-lengths and angles). Lloyd Lim (lim@iris.ucdavis.edu) has developed a "fairly efficient" (general undirected) graph layout program for the Macintosh. Greg Shannon (shannon@graph.cs.indiana.edu) writes that: THis summer two of my grad students implemented the Booth and Leuker PQ-tree planarity algorithm in Scheme. You're welcome to inspect the code and documentation. Let me know if you're interested. The input is an adacency list. Also, Mark Goldberg at rpi (goldberg@turing.cs.rpi.edu) has C program for generating an embedding from an adjacency matrix. Ramnath Sarnath (sarnath@cs.buffalo.edu) suggests looking at Fary embeddings of planar graphs, and refers to a paper in STOC88. Finally, Geoffrey (Hird oravax!geoffrey@cu-arpa.cs.cornell.edu) sent me a copy of a posting of Lloyd Lim's containing a bibliography on graph layout, together with enlightening comments (Lim's bibliography is pretty much complementary to M. Hutton's bibliography). Here it is: ----------------------------------------------------------------- The following three papers provide good surveys and/or bibliographies of graph layout problem. P. Eades and R. Tamassia, "Algorithms for Drawing Graphs: An Annotated Bibliography", Technical Report #82, Department of Computer Science, University of Queensland, Australia, 1987 R. Tamassia, G. Battista, and C. Batini, "Automatic Graph Drawing and Readability of Diagrams", IEEE Trans. Syst., Man, Cybern., SMC-18 (1988), pp. 61-79 E.B. Messinger, "Automatic Layout of Large Directed Graphs", TR 88-07-88, Department of Computer Science, University of Washington The address to write to for obtaining this one is: Dept. of Computer Science, FR-35 University of Washington Seattle, WA 98195 This is here for the hell of it. I think it's one of the first papers on graph drawing. W.T. Tutte, "How to Draw a Graph", Proc. London Math Soc., v. 3 (1963), pp 743-768 I received a copy in the mail of the following paper. I don't know if it is published or being considered for publishing at the moment. It gives O(e) algorithms for planarity testing, planar embedding, and computing the total number of different planar embeddings and an O(e log v) algorithm for finding the maximal planar subgraph of the input graph. I'm not sure if these algorithms are of practical use but they are theoretically important. The planarity algorithm is simplified while the maximal planar subgraph algorithm is a new result. J. Cai, X. Han, and R.E. Tarjan, "New Solutions to Four Planar Graph Problems" Rectilinear graph layout algorithms have been studied a lot since they are used for VLSI layout problems. The following article describes a divide and conquer framework using bifurcators. Layout area, crossing number, and minimax edge length are discussed. A good reference list for VLSI papers is included. I would say this paper is more theoretical. S.N. Bhatt and F.T. Leighton, "A Framework for Solving VLSI Graph Layout Problems", Journal of Computer and System Sciences, v. 28 (1984), pp. 300-343 The following paper describes a linear time alogrithm for recognizing and embedding planar rectilinear graphs. Psuedocode is provided. F. Hoffmann and K. Kriegel, "Embedding Rectilinear Graphs in Linear Time", Information Processing Letters, v. 29 (1988), pp.75-79 I am most interested in drawing straight line undirected graphs. This paper is the general algorithm I was looking for. The algorithm is very simple. Psuedocode is provided. I'm not sure how the speed is for large graphs since I haven't implemented it yet and the algorithm is dynamic. If anyone happens to know the email addresses of either Tomihisa Kamada or Satoru Kawai at the University of Tokyo, I would love to have them. I kind of like this approach. T. Kamada and S. Kawai, "An Algorithm for Drawing General Undirected Graphs", Information Processing Letters, v. 31 (1989), pp. 7-15 The algorithm in the following article was reported to have disappointing performance - 13 minutes for 280 nodes on a Sun 2. I think the above algorithm is slower since it takes 7.6 seconds for a regular dodecahedron (20 nodes) on a VAX 8600. Using an optimistic extrapolation based on O(v**2), it comes out to almost 25 minutes for 280 nodes on a VAX 8600. L.A. Rowe, M. Davis, E. Messinger, C. Meyer, C. Spirakis, and A. Tuan, "A Browser for Directed Graphs", Software Pract. Exper., v. 17 (1987), pp. 61-76 Mike Hutton's bibliography: ==================================== These mostly apply to directed, planar graphs; not planar graphs in general. \bibitem{ahu} {\sc A.V. Aho, J.E. Hopcroft and J.D. Ullman}, ``The Design and Analysis of Computer Algorithms", Addison-Wesley, Reading, Mass., (1974). \bibitem{birkhoff} {\sc G. Birkhoff}, ``Lattice Theory", 3rd ed. Amer. Math. Soc., Providence, R.I., (1967). \bibitem{bondy-murty} {\sc J.A. Bondy and U.S.R. Murty}, ``Graph Theory with Applications," MacMillian Co. New York, (1976). \bibitem{booth} {\sc K.S. Booth and G.S. Lueker}, Testing the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J.Comput.Syst.Sci. {\bf 13}, pp. 335-379 (1976). \bibitem{chiba-convex} {\sc N. Chiba, T. Yamanouchi and T. Nishizeki}, Linear algorithms for convex drawings of planar graphs, in {\em Progress in Graph Theory} (J.A. Bondy and U.S.R. Murty eds.) Academic Press, New York. pp. 153-173 (1984). \bibitem{chiba-draw} {\sc N. Chiba, T. Nishizeki, S. Abe and T. Ozawa}, A linear algorithms for embedding planar graphs using PQ-trees, {\em J.Comput.Syst.Sci.} {\bf 30,1}, pp. 54-76 (1985). \bibitem{chrobak} {\sc M. Chrobak}. A Linear-Time Algorithm for Drawing a Planar Graph on a Grid", Manuscript, Univ.Calif.Riverside, (1988) \bibitem{defray} {\sc H. DeFraysseix, J. Pach, and R. Pollack}. Small Sets Supporting Fary Embeddings of Planar Graphs, {\em Proc. 20'th Annual Symposium on the Theory of Computing}, pp. 426-433 (1988). \bibitem{dibattista-draw} {\sc G. DiBattista and R. Tomassia}. Algorithms for plane representations of acyclic digraphs, {\em Theoretical Computer Science} {\bf 61}, pp. 175-178 (1988). \bibitem{dibattista-hier} {\sc G. DiBattista and E. Nardelli}. An algorithm for testing planarity of hierarichical graphs, in {\em Graph-Theoretic Concepts in Computer Science}, Lecture Notes in Computer Science {\bf 246} (Springer, Berlin), pp. 277-289, (1987). \bibitem{dibattista-symmetry} {\sc G. DiBattista, R. Tomassia and I.G. Tollis}. Area Requirement and Symmetry Display in Drawing Graphs, Proc. ACM Symposium on Computational Geometry, pp. 51-60, (1989). \bibitem{even} {\sc S. Even}. {\em Graph Algorithms}, Computer Science Press, Rockville, Maryland. (1979). \bibitem{even-tarjan} {\sc S. Even and R. Tarjan}. Computing an st-numbering, Theoretical Computer Science {\bf 2}, pp. 339-344 (1976). Press, Rockville, Maryland. (1979). \bibitem{fary} {\sc I. F\'{a}ry}. On straight line representing of planar graphs. {\em Acta. Sci. Math. (Szeged)} {\bf 11}, pp. 319-321 (1948). \bibitem{hopcroft-tarjan} {\sc J. Hopcroft and R. Tarjan,} Efficient planarity testing {\em J.ACM} {\bf 21,4}, pp. 549-568 (1974). \bibitem{triconnected} {\sc H. Hopcroft and R.E. Tarjan}, Dividing a graph into triconnected components, {\em SIAM J. Comput. 2}, pp. 135-158 (1972). \bibitem{kelly} {\sc D. Kelly}, Fundamentals of planar ordered sets, {\em Discrete Math {\bf 63}}, pp. 197-216 (1987). \bibitem{kelly-rival} {\sc D. Kelly and I. Rival}, Planar Lattices, {\em Can. J. Math., Vol XXVII, No. 3}, pp. 636-665 (1975). \bibitem{mike} {\sc M.D. Hutton,} Upward Planar Drawing of Single Source Acyclic Digraphs. Masters Thesis, University of Waterloo (Sept. 1990). \bibitem{lempel} {\sc A. Lempel, S. Even, and I. Cederbaum}, An Algorithm for Planarity Testing of Graphs, in {\em Theory of Graphs, International Symposium, Rome}, P. Rosenstiehl, Ed., Gordon and Breach, N.Y. pp. 215-232 (1967). \bibitem{nishizeki} {\sc T. Nishizeki and N. Chiba}, ``Planar Graphs: Theory and Algorithms," Annals of Discrete Mathematics 32, Elsevier Science Publishing Company, Inc. New York, (1988). \bibitem{platt} {\sc C.R. Platt}, Planar Lattices and Planar Graphs, {\em J. Comb. Theory (B) {\bf 21}}, pp. 30-39 (1976). \bibitem{platt} {\sc R. Read}, New Methods for Drawing a Planar Graph Given the Cyclic order, {\em Congressus Numerantium} Vol. 56, pp. 31-44 (1976). \bibitem{schnyder} {\sc W. Schnyder}, Embeding Planar Graphs on the Grid, {\em Proc. First ACM-SIAM Symposium on Discrete Algorithms}, pp. 138-148 (1990). \bibitem{tarjan} {\sc R.E. Tarjan}, Depth-first search and linear graph algorithms, {\em SIAM J. Comput. 1,2}, pp. 146-159 (1972). \bibitem{annbib} {\sc R. Tamassia and P. Eades}, Algorithms for Drawing Graphs: an Annotated Bibliography, Brown University TR CS-89-09 (1989). \bibitem{thomassen} {\sc C. Thomassen}, Planar acyclic oriented graphs. {\em Order {\bf 5}}, pp. 349-361 (1987). \bibitem{other-thomassen} {\sc C. Thomassen}, Planarity and duality of finite and Infinite Graphs, {\em J. Combin. Theory {\bf B29}}, pp. 244-271 (1980). \bibitem{trotter} {\sc W.T. Trotter}, Graphs and partially ordered sets, in {\em Selected Topics in Graph Theory 2} (L.W. Beineke and R.J. Wilson, editors), Academic Press, New York. pp. 237-268 (1983). \bibitem{tutte-convex} {\sc W.T. Tutte}, Convex representations of graphs, {\em Proc. London Math. Soc.} Vol.10, pp. 304-320 (1960). \bibitem{tutte-draw} {\sc W.T. Tutte}, How to Draw a Graph, {\em Proc. London Math. Soc.} Vol.3, No.13, pp. 743-768 (1963). -- Igor Rivin Wolfram Research, Inc. rivin@Gang-of-Four.Stanford.EDU or rivin@wri.com ----------------------------------8<----------------------------- Bill Hahn bhahn@bogus.sw.stratus.com Stratus Computers "Instant change while you wait" - our slogan Marlboro, MA, USA Date: Wed, 8 May 91 14:29:30 +0200 From: Bert Tiems <bert@origin.nl> Subject: DAG layout algorithms I have been working on these kind of algoritms. A prototype based on the work of Sugiyama is now implemented. This prototype accepts as input an acyclic directed graph (acyclic to make layering possible, step 1 in the Sugiyama algorithm: form proper hierarchy) and greatly reduces the number of crossings (for instance, we had a graph which initially had 147 crossings and after applying the algoritm this was reduced to 5). However, it is not perfect yet. Sometimes it is clear with the naked eye that with a differnt layout the number of crossings can be re duced further. This is still something which must be worked on, but as with you we don't really need an optimal algoritm yet. By the way, most of our graphs are relatively simple (<50 nodes, < 100 crossings) and for these kinds of graphs the algoritm works well. Of course, besides reducing the number of crossings, there is also a display algorithm, which computes the physical screen representation of the resulting graph. This graph can be displayed either horizontal or vertical. We use the algoritm as a browsing tool for an object oriented database. The database objects can be visualized through selecting the corresponding graph-nodes, and the graph structure depends on the superclass/subclass relationships among the different database objects (therefore the acyclic constraint is of no problem of us because the sub/super class relations are acyclic). If you are interested in the algoritm, please let me know. Bert Tiems, bert@origin.nl ORIGIN-International Eindhoven The Netherlands Date: Wed, 8 May 91 13:39:24 PDT From: Scott Simpson <scott@wilbur.coyote.trw.com> Subject: Re: drawing Directed Acyclic Graphs (algorithm or source) Organization: MASDR Project, Redondo Beach, CA "Drawing Dynamic Trees", Sven Moen, IEEE Software, July, 1990. -- Scott Simpson TRW scott@coyote.trw.com Subject: More on DAGs Date: Thu, 9 May 91 14:51:31 EDT From: William Ricker <wdr@elf.wang.com> JOURNAL OF INFORMATION PROCESSING SOCIETY, Vol. 13, Number 4, 1990 by INFORMATION PROCESSING SOCIETY OF JAPAN ( JIPS or IPSJ ) Hoshina Bldg., 2 - 4 - 2 Azabudai, Minato - ku, Tokyo 106, Japan. CONTENT: Special Section on "Discrete Algorithms and Complexity". ++++++++ Invited Survey Papers --------------------- 424 How to Draw a Directed Graph by Peter Eades [ Univ. of Queensland, Australia ] and Kozo Sugiyama [ Fujitsu Limited ] 438 site miki.cs.titech.ac.jp, directory /JAPAN/research. [also available from cs.arizona.edu at the University of Arizona, directory japan] -- /s/ Bill Ricker wdr@wang.wang.com "The Freedom of the Press belongs to those who own one."