home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / graphics / 8288 < prev    next >
Encoding:
Text File  |  1992-07-30  |  1.3 KB  |  31 lines

  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!news.acns.nwu.edu!news.ils.nwu.edu!siegle
  3. From: siegle@ils.nwu.edu (Greg Siegle)
  4. Subject: req: crossover minimization algorithm
  5. Message-ID: <1992Jul30.174240.14953@ils.nwu.edu>
  6. Sender: usenet@ils.nwu.edu (Mr. usenet)
  7. Nntp-Posting-Host: aristotle.ils.nwu.edu
  8. Organization: The Institute for the Learning Sciences
  9. Distribution: usa
  10. Date: Thu, 30 Jul 1992 17:42:40 GMT
  11. Lines: 18
  12.  
  13. Hi there,
  14.    I'm looking for an algorithm to create a "mostly untangled" layout
  15. for arbitrary graphs. That is, given a list of vertices and
  16. connections between vertices I'd like to plot the vertices and
  17. connections on a plane minimizing edge crossings. Ideally if the
  18. algorithm is applied to a planar graph, no two edges should cross.
  19.    In a really ideal world, I'd like the algorithm to be an
  20. "anytime" algorithm such that if I stop it at any time before it's
  21. "done" it can give me what it has. The produced graph should become
  22. progressively less tangled as time passes.
  23.    I don't care so much if its really slow. 
  24.    Does such a beast exist? If you have any information regarding its
  25. whereabouts or eventual capture please mail me, as I don't read this
  26. group regularly.
  27.    Thanks very much for your help.
  28.           Sincerely,
  29.           Greg Siegle
  30.  
  31.