Graph Drawing Tools and Related Work

Literatur

• A good starting point for reasearch on graph drawing is the article G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis: Algorithms for Drawing Graphs: an Annotated Bibliography available as PostScript file (~ 116 KB) from ftp.cs.brown.edu (USA). This article was also published in Computational Geometry: Theory and Applications, no. 4, pp. 235-282, 1994.
• The conferences on graph drawing give an overview of the state of the art in graph drawing. The recent conference GD'99 was in Prague, Czechoslovakia. See R. Tamassia's graph drawing page for references about past conferences on graph drawing.

Applications

• Voyeur is a tool for the visualization of circuit information. It has many features to explore circuits to detect faults. It is able to use the VCG tool as auxiliary tool to generate routing information. See the Voyeur home page for more information.
• Oz is a concurrent constraint programming language designed for applications that require complex symbolic computations, organization into multiple agents, and soft real-time control. The DFKI Oz System allows graphical debugging of Oz terms. It is able to use the VCG tool as auxiliary tool to visualize Oz terms. See the Oz visualization page for more information.
• The Call Graph Drawing Interface is a set of small tools to visualize dynamic call graphs of C/C++ programs. It uses gprof to detect the function call structure of a test run, and uses the VCG tool to visualize this structure. It is great for debugging and documentation purposes. See the Call Graph Drawing Interface page for more information.

Graph Drawing Tools

• daVinci is a graph layout tool written in the functional language ASpecT, with a C interface. It is similar to the VCG tool but has more features to communicate with controlling programs acting as a user interface for these programs. See the daVinci home page for more information.
• GraphEd is a graph editor with a large number of algorithms concerning graphs, including automatical layout, many forms of partitionings, planarity tests etc. Libraries are also available. See the GraphEd home page for more information.
• GraphLet is the successor of GraphEd , implemented in C++ with Leda and Tcl/Tk. It provides GraphScript, a scripting language to support user interface and animation tailoring of the graph editor. Is is also the first tool that uses GML for input and output. GML is an upcoming standard for graph specifications. See the GraphLet home page for more information.
• ffGraph is a C++ graph layout library with X11 interface using Tkl/Tk. It provides automatical layout in layers and 3D spring embedding layout. The distribution includes a graph editor as example how to use the library. Unfortunately, this library is not on a ftp server but freely available on request. See the ffGraph home page for more information.
• The Edge tool was used in our project before the VCG tool was implemented. The specifications of the Edge tool and the VCG tool are nearly compatible. The Edge tool is written in C++. It is available at ftp.ira.uka.de (129.13.10.90) in the directory /pub/graphic. I don't know whether the Edge tool is still maintained, thus I don't know a contact person.
• GraphPlace is a simple and fast filter program that takes a list of nodes and edges and produces a list of coordinates of the nodes and edges, or, optionally, a PostScript picture. It is written in ANSI C with a PostScript part. It is available at ftp.dcs.warwick.ac.uk in the directory /people/Martyn.Amos. Contact J.T.J.v.Eijndhoven@ele.tue.nl for more information about GraphPlace .
• XGrab is a graph editor for directed graphs with PostScript output capabilities. The layout algorithm is similar to the standard algorithm of the VCG tool but is not very fast and has not so much parameters to control the layout algorithm. On the other hand, the layout can be improved manually very well. The tool is written in C++ and requires the Interviews package. It is available at cs.washington.edu in the directory /pub. Contact greg@cs.washington.edu for more information about XGrab .
• D-ABDUCTOR has new compound graph layout methods, including inclusion trees. It has been implemented including binaries of the toolkit XView and is delivered as a SPARC binary for Sun workstations (SunOS 4.1.x). It is available at SunSITE.sut.ac.jp (133.31.30.7), the file /pub/asia-info/japanese-src/packages/abd2.23.tar.gz. Contact misue@iias.flab.fujitsu.co.jp for more information about D-ABDUCTOR .
• VGJ is a graph layout tool written in Java. It includes tree layout, spring embedder layout and a new technique for hierarchical directed graphs by clan-based decomposition. The idea is to recognize intrinsic subgraphs (clans) by producing a parse tree of the graph, i.e. a nested relationship among the parts of the graph. The tool supports 3D and file input/output in GML, an upcoming graph specification standard. The tool is on line available; see the VGJ home page. Contact mccreary@Eng.Auburn.EDU for more information about VGJ .
• The Lens system can be used for animation and debugging of data structures. The GROOVE system is specialized for the visualization of object oriented C++ programs. Both system and various other visualization tools are developed at the GVU Center at the Georgia Institute of Technology. See the GVU home page for more information.
• Swan is a library for the visualization of C/C++ programs. A program is annotated by library calls that control the visualization sequence. Collections of data structure graphs are displayed in a simple but very functional viewer. Swan allows manual layout and provides several automatic layout algorithms including hierarchical layout, spring embedders, circular layout and special methods for trees, linear lists and arrays. Swan is useful for relatively small graphs, it requires colors and produces nice pictures in a high quality of data structure teaching textbooks. Swan is available for DecStation, demos are available for Solaris. See the Swan home page.
• The Interactive Graph Display System DG is a tool and a library of layout routines used for the display of control flow graphs, data flow graphs, expression trees, dominator trees, and more. This tool is under development. See the DG home page for more information. An application is the Data Flow Equation Display DFlow . See the Dflo home page.
• GEM3D is a tool for 3D spring embedding layout, a variant of force directed placement for undirected graphs. Here, all edges are straight and of nearly even size. GEM3D is very fast, but it is currently more a testbed for force directed placement rather than a tool for real world applications. See Arne Fricks home page for more information.
• DDD is a Data Display Debugger, a graphical frontend for GDB and DBX debuggers. It provides a graphical data display with automatic layout facilities. See the DDD home page for more information.
• ILOG offers commercial visualisation components for high performance graphics that include graph layout facilities. The ILOG Views component suite offers C++ components for Unix and MS-Windows. The ILOG JViews component suite is the Java counterpart. The graph layout capabilities among others include spring embedders, various tree layouts, orthogonal layouts and Sugiyama-style layout (hierarchical layout similar to VCG). Contact info@ilog.com for more information or visit the ILOG JViews home page. A demo applet showing some of the graph layout facilities of JViews is available here.
• The DOT tool is commercial available from AT&T. However, there is a free mail server drawdag@toucan.research.att.com where you can send a specification of your graph, and get back a PostScript or HPGL description of the graph layout. The speciality of DOT is the very good spline routine to draw smooth edges. See the Dot information page for more information.
• Other commercial graph drawing systems are available from Tom Sawyer Software, Berkely, California. There are systems and libraries for Unix and MS-Windows, mostly written in C++. Contact info@tomsawyer.com for more information or visit the Tom Sawyer Software home page.

Libraries

• The library wxWindows is a free, portable library to implement GUI for XView, Motif and all versions of MS Windows. The library has been developed by Julian Smart at the Artificial Intelligence Applications Institute of the University of Edinburgh. This library is not directly related to graph drawing. However, it is related to the VCG tool due to the fact that the VCG tool versions for MS Windows and for XView are implemented using this library.