From: mfr@Informatik.Uni-Bremen.DE. (Michael Froehlich)
Newsgroups: comp.misc
Subject: Re: Wanted: graph graphing algorithm
Date: 11 Nov 92 12:30:01 GMT
Reply-To: mfr@Informatik.Uni-Bremen.DE.
Organization: University of Bremen, Germany

In article 1dpvn4INN2ik@sal-sun107.usc.edu, ericjohn@sal-sun107.usc.edu (Eric Johnson) writes:
>
>Here's what I need: A general algorithm for graphical layout of
>graphs (nodes and arcs) which minimizes arc intersection, minimizes
>total arc lengths (under the constraints of minimum distance between
>nodes and minimum individual arc lengths), and gives a visually
>appealing layout. I'm sure that there are all sorts of other
>interesting features which would be nice (variable size nodes, a
>concept of 'gravity' which would allow this algorithm to be used to
>create standard graphs of tree structures (among other uses)), but
>those would be gravy. I've been confronted with this same problem a
>few times in the past, but before always managed to side-step it;
>not this time. I'm sure someone has already done this sort of thing,
>and I'd really appreciate it if I could stand on the shoulders of
>giants :-). Thanks in advance...

Hi Eric!

Here's a list of articles related to your "graph-layout" problem.
Perhaps the most important is [STT81]. Most of the systems described 
in the articles are based on Sugiyama's algorithm (with some important 
extensions). 
Could you please post a summary?

Michael 


[Car80]	Marie-Jose Carpano:
"Automatic Display of Hierarchized Graphs for Computer-Aided Decision 
Analysis"; IEEE Transactions on Systems, Man, and Cybernetics; Vol. SMC-10; 
No. 11; pp. 705 - 715; November 1980

[DHRT87] M. Dao, M. Habib, J.P. Richard, D. Tallot:
"CABRI, an Interactive System for Graph Manipulation"; Lecture Notes in 
Computer Science No. 246: Graph-Theoretic Concepts in Computer Science"; 
pp. 58 - 67; Springer Verlag; 1987

[GNV88]	E.R. Gansner, S.C. North, K.P. Vo:
"DAG - A Program that Draws Directed Graphs"; Software - Practice and Expe-
rience; Vol. 18(11); pp. 1047 - 1062; November 1988

[JG89]	David Jablonowski, Vincent A. Guarna:
"GMB: A Tool for Manipulating and Animating Graph Data Structures"; Soft-
ware - Practice and Experience; Vol. 19(3); pp. 283 - 301; March 1989

[NT90]	Frances Newbery-Paulisch, Walter F. Tichy:
"EDGE: An Extendible Graph Editor"; Software - Practice and Experience; Vol. 
20(S1); pp. S1/63 - S1/88; June 1990

[RDM87]	Lawrence A. Rowe, Michael Davis, Eli Messinger, Carl Meyer:
"A Browser for Directed Graphs"; Software - Practice and Experience; Vol. 
17(1); pp. 61 - 67; January 1987

[SM91]	Kozo Sugiyama, Kazuo Misue:
"Visualization of Structural Information: Automatic Drawing of Compound 
Digraphs"; IEEE Transactions on Systems, Man, and Cybernetics; Vol. SMC-21; 
No. 4; pp. 876 - 892; July/August 1991

[STT81]	Kozo Sugiyama, Shojiro Tagawa, Mitsuhiko Toda:
"Methods for Visual Understanding of Hierachical System Structures"; IEEE 
Transactions on Systems, Man, and Cybernetics; Vol. SMC-11; No. 2; pp. 109 - 
125; February 1981

[TBB88]	Roberto Tamassia, Giuseppe di Battista, Carlo Batini:
"Automatic Graph Drawing and Readability of Diagrams"; IEEE Transactions 
on Systems, Man, and Cybernetics; Vol. SMC-18; No. 1; pp. 61 - 79; January/
February 1988

[TN87]	Walter F. Tichy, Frances J. Newbery:
"Knowledge-based Editors for Directed Graphs"; Lecture Notes in Computer
Science No. 289: "Proceedings: 1st European Software Engineering Conference
ESEC'87"; pp. 101-109; Springer Verlag; 1987

---
	Dipl.-Inform. Michael Froehlich
	University of Bremen - Department of Computer Science
	PO-Box 330440, W-2800 Bremen 33, Germany
	Tel.: 	x49 421 218-4228
	e-mail: mfr@Informatik.Uni-Bremen.DE
				
I'm a recycled .signature virus. The characters of my source code
are 100% extracted from old foolish articles.
Newsgroups: comp.misc