Open Graph Drawing Framework
current version:
v.2012.07 (Sakura)

Layouts Algorithms

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
PlanarizationLayout 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
PlanarizationGridLayout 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
ClusterPlanarizationLayout The cluster planarization layout algorithm applies the planarization and topology-shape-metrics approaches to clustered graphs.
Uses: LayoutClusterPlanRepModule, CCLayoutPackModule
Multilevel Layouts
FMMMLayout The FM³ layout algorithm by Hachul and Jünger is a multilevel, force-directed layout algorithm that can be applied to very large graphs.
FastMultipoleMultilevelEmbedder 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.
ModularMultilevelMixer 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
Energy-based Layouts
SpringEmbedderFR 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.
SpringEmbedderKK 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.
DavidsonHarelLayout 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.
GEMLayout The GEM layout algorithm by Frick, Ludwig, and Mehldau.
StressMajorization An alternative to force-directed layout is distance-based layout, which is realized by the stress majorization approach.
TutteLayout 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.
Requires: COIN
Upward Layouts
SugiyamaLayout 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
UpwardPlanarizationLayout 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
DominanceLayout This is a simple upward drawing algorithm based on dominance drawings of st-digraphs.
Uses: UpwardPlanarizerModule
VisibilityLayout This is a simple upward drawing algorithm based on visibility representations.
Uses: UpwardPlanarizerModule
Planar Layouts
MixedModelLayout 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
PlanarStraightLayout 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
PlanarDrawLayout 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
Miscellaneous Layouts
BalloonLayout 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.
CircularLayout The circular layout algorithm arranges the biconnected components of the graph on circles.
Tree Layouts
TreeLayout Th tree layout algorithm is a linear-time tree layout algorithm with straight-line or orthogonal edge routing.
RadialTreeLayout 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.
tech/layouter.txt · Last modified: 2010/10/31 13:51 by carsten
This page is driven by DokuWiki