The Mixed-Model Algorithm ( MixedModelLayout )

Baseclasses

Definition

The class MixedModelLayout represents the layout algorithm Mixed-Model by Gutwenger and Mutzel [GM98], which is based upon ideas by Kant [Kan96]. In particularly, Kant's algorithm has been changed concerning the placement phase and the vertex boxes, and it has been generalized to work for connected planar graphs.

This algorithm draws a d-planar graph G on a grid such that every edge has at most three bends and the minimum angle between two edges is at least $\frac{2}{d}$
radians. G must not contain self-loops or mulitple edges. The grid size is at most $(2n-6) \times (\frac{3}{2}n-\frac{7}{2})$
, the number of bends is at most 5n - 15, and every edge has length $\protectO$(n) if G has n nodes.

The algorithm runs in several phases. In the preprocessing phase, vertices with degree one are temporarily deleted and the graph is being augmented to a biconnected planar graph using a planar biconnectivity augmentation module. Then, a shelling order for biconnected plane graphs [GM97] is computed. In the next step, boxes around each vertex are defined in such a way that the incident edges appear regularly along the box. Finally, the coordinates of the vertex boxes are computed taking the degree-one vertices into account.

General Information

Algorithm
name	Mixed-Model
long name	Mixed-Model (Gutwenger/Mutzel)
author	C. Gutwenger, P. Mutzel

Implementation
author	C. Gutwenger
date	September 1998
version	2.5

Pre- and Postcondition

precondition	=	{ planar, simple, noselfloops }
postcondition(PRE)	=	{ nocrossings }

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

$\bullet$

augmenter
an AugmentationModule option used for planar biconnected augmentation.

guaranteed precondition:	{planar, simple, noselfloops, directed}
required postcondition:	{planar, biconnected, simple, noselfloops, directed}
initial module:	PlanAug

Optional Parameters Instances of MixedModelLayout provide the following optional parameters:

$\bullet$

double base_ratio = 0.33
a double value determining, how many nodes are drawn on the base line. If base_ratio is r and the outerface is F, the number of nodes on the base line is max$\left(\vphantom{2,\min\left(\ell, r\Vert F\Vert\right)}\right.$2, min$\left(\vphantom{\ell, r\Vert F\Vert}\right.$$\ell$, r| F| $\left.\vphantom{\ell, r\Vert F\Vert}\right)$ $\left.\vphantom{2,\min\left(\ell, r\Vert F\Vert\right)}\right)$, where $\ell$ = max{k | v₁,..., v_k is a path on F_out with (v_i, v_j)$\notin$E for all j! = i + 1}.

#include < AGD/MixedModelLayout.h >

Creation

MixedModelLayout

L

creates an instance L of type MixedModelLayout.

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	L.check(const graph& G, AgdKey& p)
void	L.call(const graph& G, LayoutInterface& A)
void	L.call(const graph& G, face f, LayoutInterface& A)
void	L.call_grid(const graph& G, GridLayout& gl)
void	L.call_grid(const graph& G, face f, GridLayout& gl)
IRect	L.bounding_box()
void	L.set_mapper(const GridCoordinateMapper& gcm)

Access to Options

bool	L.set_augmenter(const AugmentationModule& M)
double	L.base_ratio()
void	L.base_ratio(double br)

Implementation

The computation of the layout takes time $\protectO$(n), where n is the number of nodes of the input graph.