Planar Biconnected ( PlanAug )

Baseclasses

Definition

Augmenting a planar graph to a planar biconnected graph by adding the minimum number of edges is an NP-hard optimization problem. Fialko and Mutzel [FM98] have suggested a 5/3-approximative polynomial time algorithm for the planar (biconnectivity) augmentation problem. An implementation of the slightly modified algorithm is presented in module PlanAug.

The algorithm first constructs a block tree T from the given graph and then iteratively adds edges between blocks of degree one in T (in a clever way). After each step an update is necessary. Although the approximation factor of 5/3 is not a good one, our experiments on a benchmark set of graphs have shown that in around 96% of all the cases our algorithm has found the optimal solution to the planar augmentation problem.

General Information

Algorithm
name	Planar Biconnected
long name	Planar Biconnected
author	S.Fialko, P. Mutzel

Implementation
author	S. Fialko
date	October 1997
version

Pre- and Postcondition

precondition	=	{ planar }
postcondition(PRE)	=	{ planar, biconnected } $\cup$ $\Big(${ simple, noselfloops } $\cap$ PRE$\Big)$

Optional Parameters Instances of PlanAug provide two parameters, which vary the optimization process. For a better solution, you should try all four possible combinations perhaps many times with permutation of the input graph. On small graphs with less than 100 nodes, the results are in most cases identical.

$\bullet$

bool size_strategy = false
Setting of size_strategy to false gives statistical better results, but differences for our test graphs were minimal (less than 1%).

$\bullet$

bool use_blabels = true
Setting use_blables to true has better approximation ratio (but not necessarily a better solution) and is a little slower.

#include < AGD/PlanAug.h >

Creation

PlanAug

A

creates an instance A of type PlanAug.

Operations

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

bool	A.check(const graph& G, AgdKey& p)
bool	A.call(graph& G)
int	A.num_added_edges()
bool	A.call(graph& G, list<edge>& L)

Access to Options

bool	A.size_strategy()
void	A.size_strategy(bool b)
bool	A.use_blabels()
void	A.use_blabels(bool b)

Implementation

The algorithm has running time $\protectO$(n³), where n is the number of nodes of the input graph.