The Quasi-Orthogonal Drawing Algorithm ( QuasiOrthogonalLayout )

Baseclasses

Definition

The class QuasiOrthogonalLayout is an implementation of an algorithm extending Tamassia's bend minimizing algorithm to the class of planar graphs with arbitrary degree [KM98b,Kla97].

The algorithm first transforms the graph to an auxiliary graph in which all the vertices have degree at most four. The idea is to internally represent all vertices with degree greater than four by an artificial region in which all adjacent vertices have degree three. In the next phase, the bend minimization algorithm for planar 4-graphs is called (see PureOrthogonalLayout [Tam87]), guaranteeing that each artificial region has rectangular shape. The last phase restores the original graph by applying the inverse of the first transformation. This guarantees that every node-induced subgraph containing vertices of degree at most four will be drawn bend-minimal and orthogonal. Hence, the algorithm generates drawings in the so-called quasi-orthogonal drawing standard [KM98b,Kla97].

General Information

Algorithm
name	Quasi-Orthogonal
long name	Quasi-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 }

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

$\bullet$

compactor
a CompactionModule option used for the compaction phase.

guaranteed precondition:	{nocrossings, orthogonal}
required postcondition:	{nocrossings, orthogonal}
initial module:	FlowCompaction

Optional Parameters Instances of QuasiOrthogonalLayout 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 QuasiOrthogonalLayout 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/QuasiOrthogonalLayout.h >

Creation

QuasiOrthogonalLayout

Q

creates an instance Q of type QuasiOrthogonalLayout.

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

Implementation

The time to compute a quasi-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.