Visualization of structural information in form of graph layout diagrams is getting increasing attention. Graphs are widely used to model relational structures such as networks, e.g., of a subway, of computers or the internet. Applications arise in economics (project management, work-flow diagrams, entity-relationship diagrams), computer science (compiler and software development tools, data base modelling, algorithm animation), social science (social networks) and natural science (flow-diagrams in Chemistry, visualization of excavations in Archeology).
A graph drawing algorithm takes as input a graph and computes a layout of the graph, i.e., a drawing in two or three-dimensional space by assigning coordinates to the vertices and mapping each edge to a simple curve. In most cases, these curves are straight lines or polygonal chains.
The layouts produced by a graph drawing algorithm should be ``aesthetically nice'' and ``easy-to-understand''. Some important criteria for readable diagrams are a small number of edge crossings, evenly distributed vertices and edges, short edges, few edge bends, a small layout area or volume, and a good angular resolution (see, e.g., [Pur97]).
There is a wide variety of graph drawing methods that take different aesthetic criteria into account. Drawing methods can be classified according to the kind of drawings they produce (e.g., hierarchical drawings, orthogonal drawings, straight-line drawings, circular drawings), the model they use (e.g., force-directed, planarization), and the class of graphs they can be applied to (e.g., planar graphs, directed acyclic graphs, trees).
AGD, a library of Algorithms for Graph Drawing, offers a broad range of existing algorithms for two-dimensional graph drawing and tools for implementing new algorithms.
In our opinion the following design goals are the most important in the field of implementing graph drawing algorithms. We try to address them in AGD as described in the following sections.
Since there are so many different approaches to graph drawing none of which can be ruled out a priori, it is important to provide the possibility of choosing among several different algorithms in order to get good results for a particular graph. Thus, systems offering only a single drawing algorithm are only of limited usefulness.
A related issue is the visualization component. Since graph drawing often appears as a subtask in a complex application, it is necessary to offer the possibility of using an arbitrary visualization component. A system for drawing graphs which is tied to a specific form of visualization significantly reduces the range of possible applications.
If a system is hard to use, then only a minority of ``expert users'' will be able to take advantage of it. Since we want to address a broad audience, we have to provide an easy interface.
Graph drawing is still a very active area of research. We want to help in closing the gap between interesting new ideas and usable software by providing a set of tools which helps in quickly and efficiently implementing new algorithms. In particular the reusage of already written modules appearing in the implementations of several graph drawing algorithms should be possible and easy. Moreover, some modules used by algorithms are exchangeable allowing to replace particular phases of an algorithm by new implementations.
New in Version 1.2
__AGD__ (defined to 12 in this version)
Please read Changes.txt and Fixes.txt in the AGD directory for more information.
© Copyright 1998-2001, Algorithmic Solutions Software GmbH. All rights reserved.
2001-08-13