home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / math / 17795 < prev    next >
Encoding:
Internet Message Format  |  1993-01-07  |  2.1 KB
  1. Xref: sparky sci.math:17795 sci.math.symbolic:3394 comp.graphics:13504
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!swrinde!gatech!udel!darwin.sura.net!jvnc.net!netnews.upenn.edu!amy.med.upenn.edu!bill
  3. From: bill@amy.med.upenn.edu (Bill Tozier)
  4. Newsgroups: sci.math,sci.math.symbolic,comp.graphics
  5. Subject: Help find optimum display of directed graphs
  6. Message-ID: <103943@netnews.upenn.edu>
  7. Date: 7 Jan 93 16:49:04 GMT
  8. Sender: news@netnews.upenn.edu
  9. Followup-To: sci.math
  10. Organization: Biology Department, University of Pennsylvania
  11. Lines: 51
  12. Nntp-Posting-Host: amy.med.upenn.edu
  13.  
  14. Hello, everyone,
  15.   I need some help with a problem in visualizing mathematical graphs.
  16. What I'm trying to do is display graphs that include numerous
  17. loops and cycles in such a way that they're easy to
  18. understand in a 2-D or 3-D image. For instance:
  19.  
  20. a -> b
  21. b -> c
  22. c -> d
  23. d -> a
  24. d -> e
  25.  
  26. is a simple digraph that would end up looking, in this
  27. "optimized" form I'm looking for, like this:
  28.  
  29.      a --> b
  30.      ^     |
  31.      |     |
  32.      |     v
  33.      d <-- c
  34.     /
  35.    /
  36.   L
  37. e
  38.  
  39.   The criteria for this are (1) that the nodes are as
  40. far from one another as can be arranged, (2) the edges
  41. are all approximately the same length, and (3) no edges
  42. are superimposed.
  43.   One can imagine the image I'd like by linking all connected
  44. nodes on this graph by, say, loose springs. The minimum
  45. energy (where "energy" is defined by the above criteria)
  46. position of all the nodes is what I'm interested in.
  47.   I've actually been trying a simpleminded optimization
  48. of the sort I just described--with springs, and the
  49. nagging suspicion that it's been done ages ago in a
  50. thorough and symbolic way is still with me.
  51.   Does anyone have any suggestions? Note that,
  52. for trees and other very sparsely connected graphs,
  53. there really isn't any problem. But for very
  54. highly connected graphs, finding a layout that
  55. is simple to "see" is extremely difficult, as
  56. numerous edges must be discernable in this project.
  57.  
  58.   Thanks for any useful advice. I'd appreciate
  59. anyone's hints re: Mathematica, or just a theoretical
  60. optimization in 2-space or 3-space.
  61.  
  62. Bill Tozier
  63. bill@amy.med.upenn.edu
  64.  
  65.