home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / misc / 4285 < prev    next >
Encoding:
Internet Message Format  |  1992-11-11  |  4.1 KB
  1. Path: sparky!uunet!dtix!darwin.sura.net!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!ira.uka.de!Germany.EU.net!ubrinf!turing!mfr
  2. From: mfr@Informatik.Uni-Bremen.DE. (Michael Froehlich)
  3. Newsgroups: comp.misc
  4. Subject: Re: Wanted: graph graphing algorithm
  5. Message-ID: <1992Nov11.123001.1279@informatik.uni-bremen.de>
  6. Date: 11 Nov 92 12:30:01 GMT
  7. References: <1dpvn4INN2ik@sal-sun107.usc.edu>
  8. Sender: news@informatik.uni-bremen.de (NEWS Service)
  9. Reply-To: mfr@Informatik.Uni-Bremen.DE.
  10. Organization: University of Bremen, Germany
  11. Lines: 82
  12. Nntp-Posting-Host: turing
  13.  
  14. In article 1dpvn4INN2ik@sal-sun107.usc.edu, ericjohn@sal-sun107.usc.edu (Eric Johnson) writes:
  15. >
  16. >Here's what I need: A general algorithm for graphical layout of
  17. >graphs (nodes and arcs) which minimizes arc intersection, minimizes
  18. >total arc lengths (under the constraints of minimum distance between
  19. >nodes and minimum individual arc lengths), and gives a visually
  20. >appealing layout. I'm sure that there are all sorts of other
  21. >interesting features which would be nice (variable size nodes, a
  22. >concept of 'gravity' which would allow this algorithm to be used to
  23. >create standard graphs of tree structures (among other uses)), but
  24. >those would be gravy. I've been confronted with this same problem a
  25. >few times in the past, but before always managed to side-step it;
  26. >not this time. I'm sure someone has already done this sort of thing,
  27. >and I'd really appreciate it if I could stand on the shoulders of
  28. >giants :-). Thanks in advance...
  29.  
  30. Hi Eric!
  31.  
  32. Here's a list of articles related to your "graph-layout" problem.
  33. Perhaps the most important is [STT81]. Most of the systems described 
  34. in the articles are based on Sugiyama's algorithm (with some important 
  35. extensions). 
  36. Could you please post a summary?
  37.  
  38. Michael 
  39.  
  40.  
  41. [Car80]    Marie-Jose Carpano:
  42. "Automatic Display of Hierarchized Graphs for Computer-Aided Decision 
  43. Analysis"; IEEE Transactions on Systems, Man, and Cybernetics; Vol. SMC-10; 
  44. No. 11; pp. 705 - 715; November 1980
  45.  
  46. [DHRT87] M. Dao, M. Habib, J.P. Richard, D. Tallot:
  47. "CABRI, an Interactive System for Graph Manipulation"; Lecture Notes in 
  48. Computer Science No. 246: Graph-Theoretic Concepts in Computer Science"; 
  49. pp. 58 - 67; Springer Verlag; 1987
  50.  
  51. [GNV88]    E.R. Gansner, S.C. North, K.P. Vo:
  52. "DAG - A Program that Draws Directed Graphs"; Software - Practice and Expe-
  53. rience; Vol. 18(11); pp. 1047 - 1062; November 1988
  54.  
  55. [JG89]    David Jablonowski, Vincent A. Guarna:
  56. "GMB: A Tool for Manipulating and Animating Graph Data Structures"; Soft-
  57. ware - Practice and Experience; Vol. 19(3); pp. 283 - 301; March 1989
  58.  
  59. [NT90]    Frances Newbery-Paulisch, Walter F. Tichy:
  60. "EDGE: An Extendible Graph Editor"; Software - Practice and Experience; Vol. 
  61. 20(S1); pp. S1/63 - S1/88; June 1990
  62.  
  63. [RDM87]    Lawrence A. Rowe, Michael Davis, Eli Messinger, Carl Meyer:
  64. "A Browser for Directed Graphs"; Software - Practice and Experience; Vol. 
  65. 17(1); pp. 61 - 67; January 1987
  66.  
  67. [SM91]    Kozo Sugiyama, Kazuo Misue:
  68. "Visualization of Structural Information: Automatic Drawing of Compound 
  69. Digraphs"; IEEE Transactions on Systems, Man, and Cybernetics; Vol. SMC-21; 
  70. No. 4; pp. 876 - 892; July/August 1991
  71.  
  72. [STT81]    Kozo Sugiyama, Shojiro Tagawa, Mitsuhiko Toda:
  73. "Methods for Visual Understanding of Hierachical System Structures"; IEEE 
  74. Transactions on Systems, Man, and Cybernetics; Vol. SMC-11; No. 2; pp. 109 - 
  75. 125; February 1981
  76.  
  77. [TBB88]    Roberto Tamassia, Giuseppe di Battista, Carlo Batini:
  78. "Automatic Graph Drawing and Readability of Diagrams"; IEEE Transactions 
  79. on Systems, Man, and Cybernetics; Vol. SMC-18; No. 1; pp. 61 - 79; January/
  80. February 1988
  81.  
  82. [TN87]    Walter F. Tichy, Frances J. Newbery:
  83. "Knowledge-based Editors for Directed Graphs"; Lecture Notes in Computer
  84. Science No. 289: "Proceedings: 1st European Software Engineering Conference
  85. ESEC'87"; pp. 101-109; Springer Verlag; 1987
  86.  
  87. ---
  88.     Dipl.-Inform. Michael Froehlich
  89.     University of Bremen - Department of Computer Science
  90.     PO-Box 330440, W-2800 Bremen 33, Germany
  91.     Tel.:     x49 421 218-4228
  92.     e-mail: mfr@Informatik.Uni-Bremen.DE
  93.                 
  94. I'm a recycled .signature virus. The characters of my source code
  95. are 100% extracted from old foolish articles.
  96.