Subject: Graph Layout in 2D

From: "LOEFFLER,DR,GERALD FEM BENAT" <[email-masked]>
Date: Tue, 6 Oct 1998 09:26:32 +0200

Hi!

I would be very thankful if you could take a second to enlighten me on
this subject:

Question:
=========

	What algorithms and implementations of these algorithms (in
	Java?) are available to "intelligently" lay out a general
	graph in 2D? The resulting layout should contain a minimum
	number of overlaps of nodes and edges.

Background:
===========

An algorithms of mine produces a general graph in the sense that the
ouput is a set of nodes {N_i} and a set of edges that connect pairs of
nodes {(N_j,N_k)}.

Every node is connected by at least one edge, i.e. there are no
unconnected nodes. Furthermore, there are no isolated "islands" that
have no connection to the rest of the graph, i.e. there is a path from
every node to every other node in the set of nodes.

I would like to automatically lay out a graph like this in 2D, such that
it looks beautiful: 1) Nodes should not overlap, and 2) edges should
cross as seldom as possible.

A description of such a layout algorithm would be fine, but an
implementation in Java that I can adapt to digest my input (set of nodes
and set of edges) would be heaven on earth (-:

My stupid solution:
===================

Having an MD background, I thought about treating the nodes as particles
that repell each other and that force the edges originating at them into
a regular polygon (e.g. 4 edges on a node would be forced to an angle of
90 degrees to each other). Then I could start with maybe all nodes on a
circle and solve Newton's equations in 2D until the layout "looks good"
(the "energy" doesn't change much)...

	thank you very much in advance!!,
	gerald

|--------------------------------------------------------------------|
 Gerald Loeffler - Bioinformatics Scientist
 Boehringer Ingelheim R&D Vienna
 Email: [email-masked]
 Phone: +43 676 3289588 (and +43 1 80105 634)
 Fax:   +43 1 80105 683
 Smail: Bender+Co, Dr. Boehringer-Gasse 5-11, A-1121 Vienna, Austria