Tutte's Algorithm ( TutteLayout )

Baseclasses

Definition

The class TutteLayout represents the layout algorithm by Tutte [Tut63].

This algorithm draws a planar graph G straight-line without crossings. It can also draw non-planar graphs.

The idea of the algorithm is to place every vertex into the center of gravity by its neighbours.

General Information

Algorithm
name	Tutte
long name	Tutte
author	W. T. Tutte

Implementation
author	D. Alberts
date	April 1997
version

Pre- and Postcondition

precondition	=	{ connected, noselfloops }
postcondition(PRE)	=	{ straight - line }

Optional Parameters Instances of TutteLayout provide the following optional parameters:

$\bullet$

DRect bbox = (0.0, 250.0, 0.0, 250.0)
a double rectangle determining the bounding box of the layout.

#include < AGD/TutteLayout.h >

Creation

TutteLayout

L

creates an instance L of type TutteLayout.

Operations

Special Functionality

bool	L.do_tutte(const leda_graph& G, LayoutInterface& a, leda_list<leda_node>& fixed_nodes, leda_list<DPoint>& fixed_positions)
		does the actual computation. fixed_nodes and fixed_positions contain the nodes with fixed positions. Precondition: All nodes in fixed_nodes are distinct and belong to G. The sizes of fixed_nodes and fixed_positions match.

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

bool	L.check(const graph& G, AgdKey& p)
void	L.call(const graph& G, LayoutInterface& A)

Access to Options

DRect	L.bbox()
void	L.bbox(const DRect& bb)

Implementation

The algorithm solves a system of linear equations and takes $\protectO$(n³) time.