The ConvexDraw Algorithm ( ConvexDrawLayout )

Baseclasses

Definition

The class ConvexDrawLayout represents the layout algorithm ConvexDraw by Marek Chrobak and Goos Kant [CK97].

This algorithm draws a planar, triconnected graph G straight-line without crossings. G must not contain self-loops or multiple edges. All faces are drawn convex, the grid layout size is at most (n - 1) x (n - 1) for a graph with n nodes (n > = 3).

The algorithm runs in two phases. In the first phase, a so-called shelling order (also called canonical ordering) for triangulated planar graphs is computed. Then, the vertices are placed incrementally according to the shelling order.

General Information

Algorithm
name	ConvexDraw
long name	ConvexDraw (Chrobak/Kant)
author	M. Chrobak, G. Kant

Implementation
author	C. Gutwenger
date	March 1997
version	2.0

Pre- and Postcondition

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

Optional Parameters Instances of ConvexDrawLayout 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 ConvexDraw 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 change the shape of the outerface (from a triangle) in order to improve the grid size of the layout.

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

Creation

ConvexDrawLayout

L

creates an instance L of type ConvexDrawLayout.

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.size_opt()
void	L.size_opt(bool so)
bool	L.side_opt()
void	L.side_opt(bool so)
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.