Path: utzoo!attcan!uunet!seismo!sundc!pitstop!sun!amdcad!ames!pasteur!ucbvax!ulysses!north
From: north@ulysses.homer.nj.att.com (Steve North[arm])
Newsgroups: comp.graphics
Subject: Re: Algorithm for graph display needed please
Summary: algorithms for drawing directed graphs
Message-ID: <10592@ulysses.homer.nj.att.com>
Date: 12 Sep 88 14:47:07 GMT
References: <8362@srcsip.UUCP>
Organization: AT&T Bell Laboratories, Murray Hill
Lines: 24


A common approach for drawing directed graphs is to rank the nodes,
then find good positions within ranks.  Here is a good place to start
reading:

	K. Sugiyama, K., S. Tagawa and M. Toda, "Methods for Visual
	Understanding of Hierarchical System Structures", IEEE Transactions
	on Systems, Man, and Cybernetics, SMC-11, No. 2, 1981,
	pp. 109--125.

Many people have been working in this area.  You might want to look
up some of the papers by Peter Eades, Larry Rowe, or M. Carpano.
Peter Eades recently has been compiling a bibliography of graph-drawing
algorithms, probably available as a tech report from the Dept. of
Computer Science, University of Queensland, St. Lucia, Queensland 4067,
Australia.

Emden Gansner, Phong Vo, and I have improved the basic Sugiyama heuristic
to get significantly better drawings in less time.  This work is described
in a tech report which you can get by writing to Stephen C North, Room 3C-539,
AT&T Bell Laboratories, 600 Mountain Ave., Murray Hill, NJ 07974;
or by sending electronic mail to north%ulysses@research.att.com

Stephen C. North