home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / theory / 1872 < prev    next >
Encoding:
Internet Message Format  |  1992-09-07  |  1.2 KB
  1. Path: sparky!uunet!mcsun!corton!loria!loria.crin.fr!eker
  2. From: eker@loria.crin.fr (Steven Eker)
  3. Newsgroups: comp.theory
  4. Subject: Re: graph-drawing algorithms needed
  5. Keywords: graph drawing algorithms
  6. Message-ID: <471@muller.loria.fr>
  7. Date: 4 Sep 92 17:54:14 GMT
  8. References: <1992Aug31.173221.6257@athena.mit.edu>
  9. Sender: news@news.loria.fr
  10. Organization: CRIN (CNRS) Nancy - INRIA Lorraine
  11. Lines: 22
  12.  
  13. In article <1992Aug31.173221.6257@athena.mit.edu>, parasite@athena.mit.edu (Vince) writes:
  14. |> 
  15. |> Hello.
  16. |> 
  17. |> A friend of mine is looking for an algorithm which will
  18. |> take the adjacency matrix of a graph in and draw or layout
  19. |> the positions of the nodes such that no two edges intersect
  20. |> in a 2-space rendition of it.  Now before you jump and say
  21. |> "Hey, this is impossible for an arbitrary graph" let me add
  22. |> that he will only be inputting graphs for which such a "picture"
  23. |> exists.  I'm not sure how he knows it exists.  
  24. |> 
  25. |> Thaaaannnnnksss.
  26. |> 
  27. |> -V
  28.  
  29. There is a discussion of just this problem & 43 refs in
  30.  
  31. J. van Leeuwen, "Graph Algorithms", Chapter 10 of Handbook of Theoretical
  32. Computer Science Volume A: Algorithms & Complexity, Elsevier, 1990.
  33.  
  34. Steven
  35.