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.
Our goals for the Open Graph Drawing Framework (OGDF) are:
- A wide range of graph and graph drawing algorithms that allow to reuse and replace particular algorithm phases by using a dedicated module mechanism.
- Sophisticated data structures, in particular those that are commonly used in graph drawing, equipped with rich interfaces.
- Self-contained code that does not require any additional libraries (except for some optional branch-and-cut algorithms).
- Portable
C++-code that supports the most important compilers for Linux, MacOS, and Windows operating systems. - Open source code available under the terms of the GNU General Public License version 2 or version 3.
History
OGDF (Open Graph Drawing Framework) went live in 2005, based on the formerly commercial OGDL (Oreas Graph Drawing Library), which is turn was heavily influenced by the LEDA-based AGD (Algorithms for Graph Drawing) library. In recent years, our library’s capabilities w.r.t. general purpose graph algorithms grew, which lead to the decision of a dual-use of the OGDF acronym as Open Graph algorithms and Data structures Framework. Over the years, it has been used in many scientific papers by various international research groups, as witnessed by Google Scholar.
Algorithms and Data Structures
OGDF provides a wider range of adaptable datastructures and algorithms, for example:
Basic graph algorithms
- efficient graph datastructures, (1/2/3-)connectivity tests, graph traversals, etc.
Embedding Algorithms
- linear-time implementations of graph decompositions in form of BC- and SPQR-trees (both static and dynamic). To our knowledge, OGDF is the only framework providing efficient implementations of the latter!
- linear-time planarity testing and embedding algorithms (Booth-Luecker and Boyer-Myrvold), including effective extraction of Kuratowski subdivisions
- optimizing planar embeddings (e.g., minimum depth, maximum external face)
Non-Planarity
- SPQR-based preprocessing algorithms (non-planar core reduction) for various non-planarity measures.
- heuristic, approximate and exact crossing minimization, with unique features like optimal edge insertion with variable embedding (see also Crossing Number Web Compute)
- The concepts are also extended to upward planarizations, simultaneous drawing and hypergraphs and the minor-monotone crossing number
- algorithms for computing planar subgraphs, graph genus
Layout algorithms
All layouts support different modules to exchange the behavior of the various substeps.
- planarization method (Topology/Shape/Metrics), including orthogonal drawings and mixed model
- Sugiyama layout (Hierachrical drawings), including algorithms for optimal node ranking, coordinate assignment, and sifting
- upward planar drawings
- planar drawings
- force-directed layouts, including the fast multipole multilevel method (FM3) for large graphs
- stress majorization and multidimensional scaling layouts
Further algorithms for…
- planar augmentations
- flows and cuts, including max flow, min cost flow, and min cut
- Steiner tree approximations (to our knowledge the only implementations of most formally strongest such algorithms)
- Voronoi regions in graphs
- efficient least-common ancestors
- clustered graphs