AGD-library: a library of algorithms for graph drawing

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 Algorithms for Graph Drawing. 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 C++ using the LEDA platform for combinatorial and geometric computing ([16, 17]). 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. (orig.)SIGLEAvailable from TIB Hannover: RR 1912(97-1-019) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekDeutsche Forschungsgemeinschaft (DFG), Bonn (Germany)DEGerman