In a Nutshell
By OGDF Team
Team & Contact
Many aspects of graph drawing research are motivated from practice, and practical evaluation of graph drawing algorithms is essential. However, graph drawing has now grown for several decades and a huge amount of algorithms for various drawing styles and applications has been proposed. Many sophisticated algorithms build upon complex data structures and other algorithms, thus making new implementations from scratch cumbersome and time-consuming. Obviously, graph drawing libraries can ease the implementation of new algorithms a lot. The LEDA-based C++-library AGD was very popular in the past, since it covers a wide range of graph drawing algorithms. However, the lack of publicly available source-code restricted the portability and extendability, not to mention the understanding of the particular implementations. Other currently available graph drawing libraries suffer from the same problems, or are even only commercially available or focus only on special graph layout methods.
Our goals for the Open Graph Drawing Framework (OGDF) were to transfer essential design concepts of AGD and to overcome its main deficiencies for use in academic research. The library provides:
A key advantage of OGDF is that it provides a wide range of adaptable layout algorithms like its customizable implementation of the planarization method. The crossing minimization module can also be used independently of the layout algorithm and provides unique features like optimal edge insertion with variable embedding, non-planar core graph reduction, etc. We also extended these well known and practically successful methods to simultaneous drawing and hypergraphs and the minor-monotone crossing number.
Most data structures and algorithms used in the implementation of the planarization approach are available as building blocks for developing new algorithms. These include planarity testing and embedding algorithms, algorithms for computing planar subgraphs, and algorithms for optimizing planar embeddings (e.g., minimum depth, maximum external face). Moreover, a recently proposed method for the extraction of a large number of Kuratowski subdivisions (which is used by the optimal crossing minimization algorithm) is provided.
The main components for optimizing over the set of all planar embeddings are the data structures BC- and SPQR-trees. OGDF contains not only efficient implementations of the static variants (such as the static SPQR-trees in AGD), but also efficient dynamic implementations. To our knowledge, this is the only implementation of dynamic SPQR-trees.
The implementation of the Sugiyama approach is also highly customizable and implements various algorithms (including optimal node ranking and coordinate assignment). Further algorithms deal with clustered graphs, planar drawing, planar augmentation, orthogonal drawing, and upward planarity, as well as force-directed layout for large graphs with the fast multipole multilevel method (FM3).