Subject: SUMMARY: Graph Layout in 2D

From: "LOEFFLER,DR,GERALD FEM BENAT" <[email-masked]>
Date: Tue, 13 Oct 1998 12:57:26 +0200

Dear CCL-ers!

Thank you for the many reponses to my question about laying out a graph
in 2D.

The question was:
=================

	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.

Summary of responses:
=====================

o This field is obviously quite established and is called "Graph
Drawing".

o Vega (http://www.ijp.si/vega/htmldoc/vinfo.htm) is a graph-theoretical
package for Mathematica that handles this and many other things. Other
packages for Mathematica are also available: http://www.mathsource.com

o A demo-applet called GraphLayout is included in SUNs JDK and
(incredibly!) slipped my attention:
http://java.sun.com/applets/jdk/1.1/demo/GraphLayout/

o Petra Mutzel and her group at Max-Planck-Institut fuer Informatik do
research on that subject and developed a library called AGD.

o DaVinci (http://www.informatik.uni-bremen.de/~davinci/) and Graphlet
(http://www.fmi.uni-passau.de/Graphlet/) are graph layout systems.

o Other relevant web pages:
http://www.cs.unisb.de/RW/users/sander/html/gstools.html
http://www.eng.auburn.edu/department/cse/research/graph_drawing/graph_dr
awing.html
http://www.fmi.uni-passau.de/~himsolt/graphdrawing.html

o Using an MD-like algorithm (as I suggested in my question) to optimize
the layout requires calculation of forces and is thus more complicated
than an MC-like algorithm.

o If the graph were in fact a chemical structure this would lead to many
additional problems regarding the conventions of drawing chemical
structures in 2D. But in fact, my problem is unrelated to chemical
structures.

Many thanks to:
===============

	Meihua Tu
	Yongxing Liu
	Darko Babic
	Stephan Reiling
	Oliver Kohlbacher
	Wolf-D. Ihlenfeldt
	Michael E. Beck
	Eric Gifford
	Peter Bladon

Many, many thanks to all of you!

	cheers,
	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