------------------------------------------------------------------------------- Here is a (light)summary of graph theory packages available on the net For drawing non-planer graphs... daVinci July 16, 1996 (Bremen, Germany) --- The University of Bremen announces daVinci V2.0.1, the revised edition of the noted visualization system for generating high-quality drawings of directed graphs with more than 1200 installations worldwide. Users in the commercial and educational domain have already integrated daVinci as user interface of their application programs for visualizing hierarchies, dependency structures, networks, configuration diagrams, dataflows, and so on. daVinci combines hierar- chical graph layout with powerful interactive capabilities and an API for remote access from a connected application. http://www.informatik.uni-bremen.de/~davinci ftp://ftp.uni-bremen.de/pub/graphics/daVinci NAUTY Brendan Mckay wrote a program called NAUTY, which has various graph theory algorithms. This program computes automorphism groups, canonically labelling and among other things. The program is for various operating systems and compilers. Brendan's email is bdm@cs.anu.edu.au CATbox Christoph Moll wrote a program for the PC called CATbox. It has a graphic interface. You can FTP it from risc3.mi.uni-koeln.de:/pub/catbox. There are actually several programs, corresponding to different graph theory problems. Christoph's email is cm@fileserv1.mi.uni-koeln.de GAP Joel Small wrote a program called GAP. It has a graphic interface. This program has many of the basic algorithms combined into one program, hence the package uses little drive space. His email is jsmall@marlin.nosc.mil graphed Michael Himsolt wrote the program 'graphed' which is for a UNIX/XWINDOWS platform. His email is himsolt@kirk.fmi.uni-passau.de The program is an extensible graph editor, with support for graph grammars. various Frank Bernhart is working on some programs. Of particular interest are programs for drawing graphs in 3-d space, and a program for constructing n-ring configurations, as used in the 4-color problem. Franks email is frb@cs.rit.edu LEDA Hermann Stamm-Wilbrandt wrote a program called LEDA. It's a collection of algorithms in C++ that one can use in writing programs. Hermann's email is hermann@holmium.informatik.uni-bonn.de Hi just reimplements this package in pure ANSI-C. There are several places to FTP it from, use archie to find one near you. EDGE The EDGE system from Francis Newberry-Paulisch. It uses the Sugiyama algorithm as basis for the layout, but its main advantage over all other systems is that the actual layout is computed by a constraint solver. Therefore, EDGE can integrate user-defined layout constraints smoothly into the Sugiyama layout. EDGE is available from ftp.ira.uka.de in pub/graphics. Unfortunately, it is not supported anymore, since F.N.P. left the University of Karlsruhe. Since then, several groups (including one at the University of Rostock, if I remember correctly) tried to extract the constraint solver from the program, because the user interface is awful and the system is very slow. VCG The VCG tool from a group at the University of Saarland. I have no personal experience with this tool, but it claims to be very fast. It's available from ftp.cs.uni-sb.de in pub/graphics/vcg. If you want to dig deeper into the literature on graph layout, you should take a look at Peter Eades and Roberto Tamassia: Algorithms for drawing Graphs: an annotated Bibliography, Technical Report CS-89-09, Brown University, Oct. 1989. -------------------------------------------------------------------------------