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