Check out this article, about GEM:

  Frick, Ludwig, Mehldau. (1995). A Fast Adaptive Layout
  Algorithm for Undirected Graphs. Retrieved March 26, 2002
  from 
http://citeseer.nj.nec.com/frick94fast.html

For xml representations of graphs, see xmlforgraphs


---------- Forwarded message ----------
Date: Fri, 22 Mar 2002 13:24:34 -0500 (EST)
From: cdent@burningchrome.com
To: katy@indiana.edu, jlbaumga@indiana.edu
Subject: notes from our gathering



It frequently helps me to clarify sit down meetings with an
after-meeting message. Like an after-dinner mint.

Makes sure we are all on the same page and such. So, find herein my
distillation of the things we talked about this morning, plus some
additional comments. Please let me know if I got anythign wrong, or
this made you think of anything. Thanks.

-=-=-

We seemed to all agree that the long range plan is a tool which does
Spring amongst nodes that can represent both clusters of documents
(using document very generally) and documents themselves with the
ability to dynamically adjust which partition of the cluster hierarchy
is being viewed, and expand nodes that represent clusters, by clicking
or similar mechanism, as needed.

We agreed that this was outside immediate scope.

We also agreed that to reach that goal a more formal and abstract data
representation and object model is required.

In that model nodes and edges become abstract representations of data
and graphical display is separated out to another layer. We hope this
will have a postive performance impact, but aren't sure. It will
certainly make the code _much_ more flexible.

To facillitate a more abstract representation, a more general input
method is needed. An XML input that supports nodes and edges strikes
me as reasonable. That's a graph. The Graph Exchange Language (GXL)
is a developing standard for such things which might be valuable.
More information about it is available here:

  GXL/">http://www.gupro.de/GXL/

(I'm particularly interested in this because it is getting a lot of
talk amongst the knowledge modelling people I've been paying attention
to lately. It may be inapppropriate for our immediate purposes, but
potentially valid in the long run.)

The immediate steps discussed are:

- modify the object model to support extensible nodes and edges in
  dataspace and graphical space
  - support several visual aspects such as color, size, shape
  - linking to external documents or resources in some fashion
    (much of this has been done in something called touchgraph.
    touchgraph is not a spring algorithm per say, but a generic
    node and edge representor:

        http://
touchgraph.sourceforge.net/

    I suspect there is a great deal that can be learned from that
    source.)

- have a hierarchical object model so that nodes can nest other nodes
  and some nodes can be considered fully leafs while others are
  containers. this should facillitate clustering: a cluster node can
  graphically represent N nodes, but just be one object on screen,
  with its own label.

- Adjust the XML representation to nodes and edges, in some fashion.

There was lot more detail on the long range view, including:

- visual cluster hierarchy adjust views
  - a slider that allows slipping up and down the hierarchy, while
    expanding or collapsing the nodes showing the clusters
    - a sort of transparent flow from one node to the nodes included is
      considered neato
- two sliders on on the interface
  - one for cluster level
  - one for edge threshhold
- click to expand clusters, with error check on large nodes

-=-=-

Okay, that's my interpretation of the high points. It's probably
different from yours given my own biases. What's different?

Thanks.

(apologies for the probably many typos)