Optimal Planar Biconnected ( OptPlanAug )

Baseclasses

Definition

The OptPlanAug module augments a planar graph to a planar biconnected graph by adding the minimum number of edges [Mut95,JM94,Fia97]. Since this problem is an NP-hard optimization problem, the algorithm may take exponential time. But on average, instances with up to 300 vertices can be solved to provable optimality within a few seconds.

The algorithm is based on branch-and-cut using ABACUS [JT97]. Branch-and-cut algorithms combine integer programming techniques like polyhedral combinatorics with a branch-and-bound scheme. The advantage of a branch-and-cut algorithm lies in improved bounding. This can be achieved by investigating the mathematical structure of the underlying polytope. For the planar augmentation problem the mathematical investigation has been done in the articles by Mutzel [Mut95], Jünger and Mutzel [JM94] and Fialko [Fia97].

General Information

Algorithm
name	Optimal Planar Biconnected
long name	Optimal Planar Biconnected
author	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 OptPlanAug inherit two parameters from PlanAug, which is used by OptPlanAug in order to find an optimal solution without branch-and-cut in advance. The following parameters vary this process:

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

Creation

OptPlanAug

A

creates an instance A of type OptPlanAug.

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)
bool	A.call(graph& G, list<edge>& L)
int	A.num_added_edges()

Access to Options

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