Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


AGD-Library: A Library of Algorithms for Graph Drawing

Alberts, David and Gutwenger, Carsten and Mutzel, Petra and Näher, Stefan

MPI-I-97-1-019. September 1997, 13 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
A graph drawing algorithm produces a layout of a graph in two- or three-dimensional space that should be readable and easy to understand.
Since the aesthetic criteria differ from one application area to another,
it is unlikely that a definition of the ``optimal drawing'' of a graph in
a strict mathematical sense exists. A large number of graph drawing algorithms
taking different aesthetic criteria into account have already been proposed.
In this paper we describe the design and implementation of the AGD--Library,
a library of {\bf A}lgorithms for {\bf G}raph {\bf D}rawing. The library
offers a broad range of existing algorithms for two-dimensional graph drawing
and tools for implementing new algorithms. The library is written in \CC using
the LEDA platform for combinatorial and geometric computing
The algorithms are implemented independently of the underlying visualization
or graphics system by using a generic layout interface.
Most graph drawing algorithms place a set of restrictions on the
input graphs like planarity or biconnectivity. We provide a mechanism
for declaring this precondition for a particular algorithm and
checking it for potential input graphs. A drawing model can be
characterized by a set of properties of the drawing. We call these properties
the postcondition of the algorithm. There is support
for maintaining and retrieving the postcondition of an algorithm.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-97-1-019.ps226 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView

URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Alberts, David and Gutwenger, Carsten and Mutzel, Petra and N{\"a}her, Stefan},
  TITLE = {AGD-Library: A Library of Algorithms for Graph Drawing},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-97-1-019},
  MONTH = {September},
  YEAR = {1997},
  ISSN = {0946-011X},