What follows is a list of layout algorithms available using BLAG. For each algorithm we give: code, short description, time complexity notes, and pre-conditions.

Code Description Time Preconditions
0 QuickOrthogonal
Based on a visibility representation of the given embedding, with a bend-minimization heuristic. A min-cost-flow compaction technique is also applied to minimize edge lengths.
O(n) 4-degree AND biconnected.
1 OptimalOrthogonal
Based on a bend-minimization min-cost-flow technique. A min-cost-flow compaction technique is also applied to minimize edge lengths. Returns the orthogonal layout with the minimum number of bends for the given embedding.
O(n2 log n) No preconditions.
2 SlowOrthogonal
Based on a bend-minimization min-cost-flow technique applied on embeddings generated with a branch-and-bound technique by means of an SPQR-tree. A min-cost-flow compaction technique is also applied to minimize edge lengths. Returns the orthogonal layout with the minimum number of bends over all the planar embeddings.
O(exp(n)) Biconnected AND planar.
3 OptimalUpward
Based on a bend-minimization min-cost-flow technique. A min-cost-flow compaction technique is also applied to minimize edge lengths. Returns the quasi-upward layout with the minimum number of bends for the given embedding.
O(n2 log n) Directed.
4 SlowUpward
Based on a bend-minimization min-cost-flow technique applied on embeddings generated with a branch-and-bound technique by means of an SPQR-tree. A min-cost-flow compaction technique is also applied to minimize edge lengths. Returns the quasi-upward layout with the minimum number of bends over all the planar embeddings.
O(exp(n)) Biconnected AND directed AND bimodal AND planar.
5 OptimalUpwardVisbility
Oriented visibility representation of a layout generated by the OptimalUpward algorithm.
O(n2 log n) Directed.
6 SlowUpwardVisibility
Oriented visibility representation of a layout generated by the SlowUpward algorithm.
O(exp(n)) Biconnected AND directed AND bimodal AND planar.
7 Polyline
Based on the visibility algorithm. Returns a polyline layout with at most two bends per edge.
O(n) Biconnected.
8 Visibility
Based on st-numbering. A min-cost-flow compaction technique is also applied to minimize edge lengths. Returns an unoriented visibility representation.
O(n) Biconnected.
9 TreeCenterSons
Returns a hierarchical representation in which each node is above and horizontally centered with respect to its sons.
O(n) Acyclic (regardless edge directions).
10 TreeCenterSubtree
Returns a hierarchical representation in which each node is above and horizontally centered with respect to its whole subtree.
O(n) Acyclic (regardless edge directions).


Last update : July 31, 2002
Website design by INTEGRA Sistemi, www.IntegraSistemi.it