rivin@Gang-of-Four.Stanford.EDU (Igor Rivin) (08/28/90)
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
martin@cs.umn.edu (Johnny Martin) (08/29/90)
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 --
hmueller@wfsc4.tamu.edu (Hal Mueller) (08/29/90)
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
rt@cs.brown.edu (Roberto Tamassia) (08/29/90)
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
boykett@wacsvax.cs.uwa.OZ.AU (Tim Boykett) (09/03/90)
Yopu said you didn't want a planar testing alg, but one of the algs I looked into earlier this year for testing planarity resulted in a structure of some kind that ordered the arcs incident with a point clockwise aound the point; this would make the grapoh easy to draw, I would think. Tell me if you'd like the reference Tim.