Open Graph Drawing Framework
current version:
v.2010.10 (Sassafras)
     

Key Features

The following is a short and incomplete list of the main algorithms and datastructures in OGDF. Many algorithms are encaspulated into Modules, such that other algorithms can easily switch between multiple different Algorithms for the same subproblem:

  • Basic Algorithms
    • 2-connectivity decomposition and BCTree, also DynamicBCTree
    • Min-Cost-Flow
    • Minimum Cut
    • Shortest Path
    • etc.
  • Sophisticated Algorithms and Data Structures
    • linear-time implementation of 3-connectivity decomposition and SPQRTree, also DynamicSPQRTree
    • linear-time Planarity testing: the traditional Chiba, Nishizeki, Abe, Ozawa algorithm based on PQ-trees, and the fast BoyerMyrvold, including a linear algorithm to extract multiple Kuratowski-subdivisions at once.
    • linear-time Upward-Planarity testing of sT-graphs
    • Cluster-Planartiy testing of c-connected cluster graphs
    • EmbedderMinDepthMaxFace
    • linear-time NonPlanarCore Reduction
    • linear-time edge insertion over all embeddings (VariableEmbeddingInserter), and SubgraphPlanarizer, the currently best known crossing minimization heuristic. Also suitable for Simultaneous Crossing Minimization and Minor Monotone Crossing Minimization.
    • Planar 2-connected Augmentation
 
ogdf/features.txt · Last modified: 2011/05/03 15:05 by carsten
This page is driven by DokuWiki