1displaying graphs0

["J. Scott Penberthy" <JSP@ibm.com>]

Beng-Hong,

I've got a graph Browser that let's someone peruse a directed graph; its
got a 2d, reshapeable cursor so that you can control both (1) the number
of nodes seen in a window, and (2) the portion of the graph seen in a
window.  This browser also allows you to (optionally) specify how the
nodes should appear (i.e. their shape + their contents).

I use a simple layout routine that draws all graphs in a tree format.
Cycles within the graph are handled by either duplicating a node that
starts a cycle, or by drawing lines across the tree structure.  Although
I can't distribute my software (IBM's rules), Gabe Robins at ISI devised
a similar browser that he sells for about $150. His browser is called
the "ISI Grapher," and it uses the same algorithm that I use.

I'm sorry that I can't include the algorithm here -- Gabe, on the other
hand, details the algorithm on pages 24 and 25 of the ISI Grapher
manual.  You can obtain the manual by writing to Gabe at

                 Gabriel Robins
             Information Sciences Institute
            The Intelligent Systems Division
               4676 Admiralty Way
         Marina Del Rey, California 90292-6695

In your letter you also said that you wanted an algorithm that "should
strive to minimize edge crossings and edge lengths and also handle
manhattan routing."  Such an "optimal layout" algorithm for an arbitrary
graph would probably take much more power than the Symbolics can offer.
You might have better luck devising a special-purpose algorithm for your
own directed graphs; most layout routines take advantage of some aspect
of the underlying graph structure.  For example, I chose a tree layout
since my graphs have few cycles; that may or may not be useful to you.
If you have a highly interconnected graph, you might want to contact the
VLSI group at MIT and ask them about their layout algorithms.

Good luck!

Cheers,
Scott