The Orthogonal Drawing Algorithm ( OrthogonalLayout )

Baseclasses

Definition

The class OrthogonalLayout is an implementation of an algorithm extending Tamassia's bend minimizing algorithm to the class of planar graphs with arbitrary degree [KM98b,Kla97]. It differs from the implementation of the class QuasiOrthogonalLayout only in its output style.

In an orthogonal drawing, vertices of degree greater than four are drawn as boxes whose corner points are mapped to grid points. The internal computations are the same as in the classes QuasiOrthogonalLayout and PureOrthogonalLayout.

General Information

Algorithm
name	Orthogonal
long name	Orthogonal Layout
author	G. W. Klau, P. Mutzel

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

Pre- and Postcondition

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

Exchangeable Modules Instances of type OrthogonalLayout 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 OrthogonalLayout 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 OrthogonalLayout 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/OrthogonalLayout.h >

Creation

OrthogonalLayout

O

creates an instance O of type OrthogonalLayout.

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	O.check(const graph& G, string& message)
void	O.call(const graph& G, LayoutInterface& A)
void	O.call(const graph& G, face f, LayoutInterface& A)
void	O.call(PlaneGraphCopy& PG, face f, LayoutInterface& A)
void	O.call_grid(const graph& G, GridLayout& gl)
void	O.call_grid(const graph& G, face f, GridLayout& gl)
void	O.call_grid(PlaneGraphCopy& PG, face f, GridLayout& gl)
IRect	O.bounding_box()
void	O.set_mapper(const GridCoordinateMapper& gcm)

Implementation

The time to compute an orthogonal drawing is O((nlogn)²) where n is the number of vertices in the graph to be drawn. It is thus asymptotically equal to the time to compute a PureOrthogonalLayout.