First Page

News

In a Nutshell

About OGDF

FAQs

Key Features

Publications

Documentation

Overview Pages

How-Tos

Developer Resources

Reference Documentation

Get OGDF

Download

Installation (Linux/Mac)

Installation (Windows)

Projects using OGDF

Team & Contact

Imprint

Datenschutz

Table of Contents

This page gives an overview about the various modules in OGDF used by layout algorithms. Modules not used with any layout algorithm are omitted here. For further information, click on the class name of the module base class or the class of a specific implementation.

This overview page is structured according to general modules, planarity-based layouts, multilevel layouts, planar layouts, and upward layouts.

These modules are used by various layout algorithms.

CCLayoutPackModule | A arranges the layouts of the connected components of a graph, thereby obtaining a layout of the whole graph. |
---|---|

| The packs the components into rows and respects a given aspect ratio. tile-to-rows algorithm |

These modules are used by planarity-based algorithms, in particular by algorithms applying the planarization approach.

**See classes:**

, *PlanarizationLayout*

, and *PlanarizationGridLayout**ClusterPlanarizationLayout*

PlanarSubgraphModule | A computes a planar subgraph of an input graph G by determining which edges in G must be removed. |
---|---|

| The algorithm is based on PQ-trees. It is fast and usually achieves very good results, especially when using randomization option. fast planar subgraph |

| This algorithm computes a by simply adding edges incrementally and testing planarity each time; if the graph becomes non-planar, the just inserted edge is removed.maximal planar subgraphThis approach always computes a maximal planar subgraph, but is quite slow in practice and usually cannot achieve better results than FastPlanarSubgraph. |

| The branch-and-cut-based exact algorithm computes a , i.e., the largest possible planar subgraph.maximum planar subgraphRequires: COIN and ABACUS |

EdgeInsertionModule | An re-inserts edges previously removed to make a graph planar, resulting in a planarized representation of the original graph. |

| The is the standard approach for edge insertion. It simply fixes an embedding and inserts the edges by computing shortest paths in the dual graph. Each edge insertion requires linear runtime. The quality of the solutions can significantly be improved using postprocessing and random permutations. fixed-embedding inserter |

| The applies the optimal one-edge insertion algorithm. It finds the best embedding for inserting an edge with the least crossings in linear runtime. It also supports postprocessing and random permutations to improve solution quality when inserting serveral edges. variable-embedding inserter |

EmbedderModule | An computes a planar embedding of a planar graph. |

| The simply encapsulates a standard planar embedding algorithm. simple embedder |

| The computes a planar embedding with a largest possible external face in linear time. max-face embedder |

| The computes a planar embedding with minimal block-nesting depth in linear time. The min-depth embedderblock-nesting depth is a measure for the nesting of biconnected components (blocks) in the planar embedding. |

| The computes a planar-embedding with minimal block-nesting depth for given embeddings of the biconnected components. The algorithm takes linear time. min-depth-PiTA embedder |

| The combines the min-depth and max-face embedder. It computes a planar embedding with minimal block-nesting depth, which has the largest external face. The algorithm takes linear time. min-depth max-face embedder |

| The is an improved version of the max-face embedder, which also tries to unfold inner parts. max-face-layers embedder |

| The combines the min-depth and max-face-layers embedders, similar as the min-depth max-face embedder. min-depth max-face-layers embedder |

LayoutPlanRepModule | A is a planar layout algorithm which gets a as input. |

| The algorithm is based on bend minimization using network flow algorithms; it also supports high-degree vertices of arbitrary size and applies sophisticated orthogonal compaction techniques. orthogonal layout |

GridLayoutPlanRepModule | A is a planar grid layout algorithm which gets a as input. |

| The is a linear-time algorithm that produces polyline drawings with few bends and good angular resolution.mixed-model layoutUses: EmbedderModule, AugmentationModule, ShellingOrderModule, MixedModelCrossingsBeautifierModule |

LayoutClusterPlanRepModule | A is a planar layout algorithm which gets a as input. |

| The algorithm is also based on bend minimization using network flow algorithms, supports high-degree vertices of arbitrary size, and applies sophisticated orthogonal compaction techniques. cluster orthogonal layout |

These modules are used within the modular multilevel-layout framework.

**See class:** *ModularMultilevelMixer*

MultilevelBuilder | A constructs a multilevel hierarchy, represented as a |
---|---|

| The simply selects vertices randomly and merges them with a random neighbor, until the size of the graph decreases by a predefined factor. random merger |

| The computes a matching by visiting the vertices in a random order, matching each unmatched vertex with a random unmatched neighbor if one exists. matching merger |

| The is a variant of the matching merger intended to eliminate that for star-like structures a linear number of levels may be necessary. In addition to the matching, an edge cover is computed such that each contained edge is incident to at least one unmatched vertex. These cover edges are then used to merge their end points. edge-cover merger |

| The is a variant of the edge cover merger that tries to avoid loss of biconnectivity in the local neighborhoods around the merging positions. local-biconnected merger |

| The corresponds to the method used in the FM³ algorithm, where the vertices are partitioned into solar mergersolar systems, classifying each vertex as either sun, planet, or moon. The resulting solar systems are then collapsed to their sun vertex. |

| The corresponds to the strategy within the GRIP approach, which is based on maximal independent set filtrations. independent-set merger |

InitialPlacer | An computes an initial placement for vertices in a multilevel layout algorithm |

| The simply places a vertex at the same position as its representative in the previous level, with a small random offset to avoid zero distances between vertices. zero placer |

| The places vertices at random positions within the smallest circle containing all vertices around the barycenter of the current drawing.random placerThis is usually a bad strategy, and other placers should be used instead! |

| The places a vertex at the barycenter of its neighbor's positions. barycenter placer |

| The is an alternative to the barycenter places; it uses the median of the neighbor positions for each coordinate axis. median placer |

| The corresponds to the approach in the FM³ algorithm and uses information from the solar merger. A new vertex is placed on the direct line between two suns at the relative position with respect to its position on the intersystem path between these suns.solar placerPlease note: In combination with other mergers, the solar merger is equivalent to the zero placer. |

These modules are used with planar straight- and polyline algorithms. The crossings beautifier modules are only relevant when drawing planarized representations of a graph, where certain vertices represent edge crossings in the final drawing.

**See classes:**

, *MixedModelLayout*

, and *PlanarDrawLayout**PlanarStraightLayout*

AugmentationModule | An adds edges to a graph to obtain a certain connectivity. |
---|---|

| This algorithm is based on . If the input graph is planar, the augmented graph will also remain planar. depth-first search |

| The algorithm augments a planar graph to a planar biconnected graph. The implementation is based on the algorithm by Fialko and Mutzel. It gives much better solutions than the DFS-based algorithm, usually close to the optimum. planar augmentation |

ShellingOrderModule | A computes a shelling order of a planar graph. |

| This algorithm computes a shelling order for a graph. biconnected planar |

| This algorithm computes a shelling order for a graph. triconnected planar |

MixedModelCrossingsBeautifierModule | A is used within for improving the layout of vertices representing crossings in the final drawing. |

| The does not do any beautification at all. It can be used to obtain the original mixed-model algorithm. dummy crossings beautifier |

| The crossings beautifier simply doubles the grid. double-grid |

| The crossings beautifier uses a local stretch strategy. local-stretch |

These modules are used with layout algorithms for producing upward drawings of (acyclic) digraphs.

**See classes:**

and *SugiyamaLayout*

, as well as *UpwardPlanarizationLayout*

and *DominanceLayout**VisibilityLayout*

RankingModule | A computes a layering of a directed graph. |
---|---|

| The produces a layering whose height is the length of a longest path in the digraph. The implementation contains a special optimization for reducing the lengths of unnecessary long edges.longest-path rankingUses: AcyclicSubgraphModule |

| The algorithm computes a layering with minimal edge spans. It is based on an ILP-formulation and implemented using network flow.optimal rankingUses: AcyclicSubgraphModule |

| The algorithm computes a layering with small height for a given maximal layer widths (number of nodes on a layer).Coffman-Graham rankingUses: AcyclicSubgraphModule |

AcyclicSubgraphModule | An computes an acyclic subgraph of an input graph by determining a set of edges to be removed. |

| The based algorithm simply removes the back edges in a DFS-tree. The linear-time algorithm is fast, but it might remove significantly more edges than necessary. depht-first-search |

| The algorithm applies the greedy heuristic by Eades and Lin to compute a maximal acyclic subgraph. The quality of the solution is usually better than the one obtained by the simple DFS-based approach. The algorithm takes linear time as well. greedy-cycle-removal |

TwoLayerCrossMin | A module minimizes the crossings between two layers in a layered graph, where one layer is fixed and the other layer shall be reordered. |

| The computes for each vertex the barycenter heuristicbarycenter (average) of the positions of its neighbors on the fixed layer, and then sorts the vertices according to this value. |

| The computes for each vertex the median heuristicmedian of the positions of its neighbors on the fixed layer, and then sorts the vertices according to this value. |

| The chooses a pivot vertex split heuristicv, and places every other vertex to the left or right of v according to whether it would make fewer crossings. This step is applied recursively to order the left hand set and the right hand side of v. |

| The … sifting heuristic |

| The … greedy-switch heuristic |

| The … greedy-insert heuristic |

HierarchyLayoutModule | A assigns coordinates to vertices and bend points in a . |

| The module implements the coordinates assignment algorithm by Buchheim, Jünger, and Leipert. It guarantees that all edges will have at most two bends, and for each edge with exactly two bends that the segment between them is drawn vertically. fast hierarchy layout |

| The module implements the coordinates assignment algorithm by Brandes and Köpf. fast-simple hierarchy layout |

| The is based on an LP-formulation. It provides similar optimizations for long edges as the fast hierarchy layout module, in particular edges will have at most two bends.optimal hierarch layoutRequires: COIN |

UpwardPlanarizerModule | An computes an upward planarized representation of an input graph. |

| Uses: FUPSModule, UpwardEdgeInserterModule, AcyclicSubgraphModule |

FUPSModule | A computes a feasible upward planar subgraph. |

| The module computes a feasible upward planar subgraph using the algorithm by Chimani, Gutwenger, Mutzel, and Wong. FUPS-simple |

UpwardEdgeInserterModule | An re-inserts edges into an upward planarized representation. |

| The reinserts edges into a fixed upward planar embedding. fixed-embedding upward edge inserter |

UPRLayoutModule | An computes a layout of an upward planarized representation. |

| The computes a layered hierarchy and applies a hierarchy layout module as within the Sugiyama algorithm.layer-based UPR layouterUses: RankingModule, HierarchyLayoutModule |

tech/modules.txt · Last modified: 2014/12/16 12:20 (external edit)

This page is driven by DokuWiki