In a Nutshell
Projects using OGDF
Team & Contact
Many OGDF layout algorithms can be customized through module options, which allow to easily replace the implementation of a specific step of the algorithm. This pages gives an overview about the various layout algorithms contained in OGDF and lists the available module options for each algorithm. These modules are then listed on a separate module overview page.
|General Orthogonal and Polyline Layouts|
| The planarization layout algorithm applies the planarization approach for crossing minimization, combined with the topology-shape-metrics approach for orthogonal planar graph drawing. It produces drawings with few crossings and is suited for small to medium sized sparse graphs.
Uses: PlanarSubgraphModule, EdgeInsertionModule, EmbedderModule, LayoutPlanRepModule, CCLayoutPackModule
| The planarization grid layout algorithm is similar as planarization layout, but uses a planar grid layout algorithm to produce a drawing on a grid.
Uses: PlanarSubgraphModule, EdgeInsertionModule, GridLayoutPlanRepModule, CCLayoutPackModule
| The cluster planarization layout algorithm applies the planarization and topology-shape-metrics approaches to clustered graphs.
Uses: LayoutClusterPlanRepModule, CCLayoutPackModule
|The FM³ layout algorithm by Hachul and Jünger is a multilevel, force-directed layout algorithm that can be applied to very large graphs.|
|The FMME layout algorithm is a variant of multilevel, force-directed layout, which utilizes various tools to speed up the computation. It can also make use of SSE-instructions and multicore processors.|
| The modular multilevel-mixer is a general framework for multilevel graph layout. The different steps of the multilevel approach (coarsening, initial placement, and single-level layout) can be customized through module options.
Uses: LayoutModule, MultilevelBuilder, InitialPlacer
|The Fruchterman-Reingold layout algorithm is a typical force-directed layout algorithm; this version implements the grid-variant of the algorithm to speed up the computation of repulsive forces.|
|The Kamada-Kawai layout algorithm is a force-directed layout algorithm that tries to place vertices with a distance corresponding to their graph theoretic distance.|
|The Davidson-Harel layout algorithm uses simulated annealing to find a layout of minimal energy. Due to this approach, the algorithm can only handle graphs of rather limited size.|
|The GEM layout algorithm by Frick, Ludwig, and Mehldau.|
|An alternative to force-directed layout is distance-based layout, which is realized by the stress majorization approach.|
| One of the oldest layout algorithms has been proposed by Tutte; it simply fixes some external vertices and places the other vertices in the barycenter of their neighbors.
| The classical, layer-based approach for producing upward drawings is the algorithm by Sugiyama, Tagawa, and Toda. It consists of three steps (in our case four, since we place connected components separately) which can all be customized through module options: Assign vertices to levels (ranking), minimize crossings by permuting the vertices on the layers, and finally compute coordinates.
Uses: RankingModule, TwoLayerCrossMin, HierarchyLayoutModule, CCLayoutPackModule
| The upward-planarization layout algorithm is an alternative to the classical Sugiyama approach. It adapts the planarization approach for hierarchical graphs and produces significantly less crossings than Sugiyama layout. It also provides various module options for customization.
Uses: UpwardPlanarizerModule, UPRLayoutModule
| This is a simple upward drawing algorithm based on dominance drawings of st-digraphs.
| This is a simple upward drawing algorithm based on visibility representations.
| The mixed-model layout algorithm is a polyline drawing algorithm for planar graphs. It routes edges with at most three bends per edge and guarantees a grid size of at most (2n-6) * (3/2n-7/2), where n is the number of vertices.
Uses: EmbedderModule, AugmentationModule, ShellingOrderModule, MixedModelCrossingsBeautifierModule
| The planar-straight layout algorithm is a straight-line drawing algorithm for planar graphs. It draws a planar graph with n vertices on a grid of size at most (2n-4) * (n-2) without edge crossings.
Uses: AugmentationModule, ShellingOrderModule
| The planar-draw layout algorithm is also a straight-line drawing algorithm for planar graphs, which produces compacter drawings. It draws a planar graph with n vertices on a grid of size at most (n-2) * (n-2) without edge crossings.
Uses: AugmentationModule, ShellingOrderModule
|The balloon layout algorithm places each vertex's children in its enclosing circle (centered at the root vertex). The vertices are placed to avoid overlapping between vertices and to make the layout compact.|
|The circular layout algorithm arranges the biconnected components of the graph on circles.|
|Th tree layout algorithm is a linear-time tree layout algorithm with straight-line or orthogonal edge routing.|
|The radial-tree layout algorithm produces radial tree layouts in linear-time, i.e, the root is drawn in the center and the levels are arranged on concentric circles around the root.|