|
Description: |
> |
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.
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. It is a product of a cooperation of
groups in Halle, Köln and Saarbrücken supported by the DFG in the
program ``Effiziente Algorithmen für diskrete Probleme und ihre
Anwendungen''.
The two main parts of AGD are a collection of layout algorithms and a
toolbox for extending the library by new implementations.
AGD contains classical graph drawing algorithms as well as
implementations of new algorithms (in some cases extensions of the
former), that have been developed within the DFG project. In
particular, AGD is designed to support planar graph drawing
algorithms and planarization methods in a flexible way. Moreover, AGD
contains exact algorithms using for NP-hard
optimization problems occuring in graph drawing, e.g., crossing
minimization, maximum planar subgraph. | |
