The PlanarDraw Algorithm ( PlanarDrawLayout )

Baseclasses

Definition

The class PlanarDrawLayout represents the layout algorithm PlanarDraw (Gutwenger and Mutzel [GM97]), which is a generalization of the algorithm ConvexDraw (Chrobak and Kant [CK97]).

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 at most (n - 1) x (n - 1) 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 biconnected plane graph (using a planar biconnectivity augmentation module). Then, a new shelling order [GM97] (also called canonical ordering) for biconnected planar graphs is computed. In the third phase the vertices are placed incrementally according to the shelling order.

General Information

Algorithm
name	PlanarDraw
long name	PlanarDraw (Gutwenger/Mutzel)
author	C. Gutwenger, P. Mutzel

Implementation
author	C. Gutwenger
date	March 1997
version	1.0

Pre- and Postcondition

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

Exchangeable Modules Instances of type PlanarDrawLayout 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}
initial module:	PlanAug

Optional Parameters Instances of PlanarDrawLayout provide the following optional parameters:

$\bullet$

bool size_opt = true
a boolean value determining if the grid size of the layout is optimized compared to the original Convex algorithm. This option reduces the grid size especially for graphs with few edges. If the graph is (almost) triangulated, the grid size will be (almost) the same.

$\bullet$

bool side_opt = false
a boolean value determining if it is allowed to have slopes other than -1, 0, +1 on the outerface.

$\bullet$

bool max_outer = true
a boolean value determining if the algorithm chooses the face of G with maximal degree as outerface (true), or the first face in the list of faces.

$\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/PlanarDrawLayout.h >

Creation

PlanarDrawLayout

L

creates an instance L of type PlanarDrawLayout.

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(AugmentationModule& M)
bool	L.size_opt()
void	L.size_opt(bool so)
bool	L.side_opt()
void	L.side_opt(bool so)
bool	L.max_outer()
void	L.max_outer(bool mo)
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.