The de Fraysseix, Pach, Pollack Algorithm ( FPPLayout )

Baseclasses

Definition

The class FPPLayout represents the layout algorithm by de Fraysseix, Pach, Pollack [DPP90].

This algorithm draws a planar graph G straight-line without crossings. G must not contain self-loops or multiple edges. The grid layout size is (2n - 4) x (n - 2) for a graph with n nodes (n > = 3).

The algorithm runs in three phases. In the first phase, the graph is augmented by adding new artificial edges to get a triangulated plane graph. Then, a so-called shelling order (also called canonical ordering) for triangulated planar graphs is computed. In the third phase the vertices are placed incrementally according to the shelling order.

General Information

Algorithm
name	de Fraysseix et al.
long name	de Fraysseix, Pach, Pollack
author	H. de Fraysseix, J. Pach, R. Pollack

Implementation
author	C. Gutwenger
date	February 1997
version	1.0

Pre- and Postcondition

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

#include < AGD/FPPLayout.h >

Creation

FPPLayout

L

creates an instance L of type FPPLayout.

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)

Implementation

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