The Pure Orthogonal Drawing Algorithm ( PureOrthogonalLayout )

Baseclasses

Definition

The class PureOrthogonalLayout is an implementation of Tamassia's bend minimizing algorithm for the class of 4-planar graphs [Tam87]. In addition to planarity, these graphs have the property that no vertex has more than four neighbours. Note that pure orthogonal drawings in which the vertices are mapped to points in the grid are only admissible for 4-graphs. For arbitrary planar graphs we provide two extensions of the orthogonal standard: They are realized by the classes QuasiOrthogonalLayout and OrthogonalLayout.

The computation of the layout follows the so-called Topology-Shape-Metrics approach [DETT99]. The input is a 4-planar graph with fixed topology. According to this topology the algorithm constructs a network. A minimum-cost flow in this network determines a bend-minimal orthogonal representation for the input graph. In a last phase, one of the available compaction modules assigns lengths to this representation and thus fixes the coordinates of the drawing.

General Information

Algorithm
name	Pure Orthogonal
long name	Pure Orthogonal Layout
author	R. Tamassia

Implementation
author	G. W. Klau
date	April 1999
version	1.1

Pre- and Postcondition

precondition	=	{ planar, simple, noselfloops, four - - graph}
postcondition(PRE)	=	{ no crossings, orthogonal }

Exchangeable Modules Instances of type PureOrthogonalLayout provide the following module options:

$\bullet$

compactor
a CompactionModule option used for the compaction phase.

guaranteed precondition:	no crossings, orthogonal
required postcondition:	no crossings, orthogonal
initial module:	FlowCompaction

Optional Parameters Instances of PureOrthogonalLayout provide the following optional parameters:

$\bullet$

int output_level = 0
The output_level determines the amount of output to stdout that is produced by the algorithm. The default value, zero, causes PureOrthogonalLayout to run in silent mode, values > = 10 cause the maximal amount of output.

$\bullet$

bool verify = true
If this flag is set, the checking routines are activated. Especially the orthogonal representation is verified, certificating the correctness of the computation.

#include < AGD/PureOrthogonalLayout.h >

Creation

PureOrthogonalLayout

P

creates an instance P of type PureOrthogonalLayout.

Operations

Standard Interface (Inherited Methods) The detailed description of these methods can be found in the manual entries of the base classes (LayoutModule, GridLayoutModule).

bool	P.check(const graph& G, string& message)
void	P.call(const graph& G, LayoutInterface& A)
void	P.call(const graph& G, face f, LayoutInterface& A)
void	P.call(PlaneGraphCopy& PG, face f, LayoutInterface& A)
void	P.call_grid(const graph& G, GridLayout& gl)
void	P.call_grid(const graph& G, face f, GridLayout& gl)
void	P.call_grid(PlaneGraphCopy& PG, face f, GridLayout& gl)
IRect	P.bounding_box()
void	P.set_mapper(const GridCoordinateMapper& gcm)

Implementation

The computation of a pure orthogonal grid embedding by algorithm PureOrthogonalLayout takes time O((nlogn)²) where n is the number of nodes of the graph to be drawn.

Example

The following program shows how to use the pure orthogonal layout algorithm in combination with a TopologyModule which preserves the eventual planar topology of the input. The user can draw or load a graph in a GraphWin, pressing the ``done'' button initiates the layout process. If the input drawing divides the plane into faces, the same faces will emerge in the output drawing (i.e., the topological representation and the external face will be preserved during the computations).

#include <AGD/TopologyModule.h>
#include <AGD/PureOrthogonalLayout.h>
#include <AGD/GraphWinInterface.h>
#include <LEDA/graphwin.h>

main() {
  
GraphWin W; W.display();

while (W.edit()) {
  
GraphWinInterface I(W);
graph& G = W.get_graph(); face f_0; string msg;
TopologyModule T; PureOrthogonalLayout P;
T.call(G, f_0, I);
if (P.check(G, msg)) P.call(G, f_0, I);
else W.acknowledge(msg);
W.fill_window();

}

}