LEDA's Make Biconnected ( LEDAMakeBiconnected )

Baseclasses

Definition

The LEDAMakeBiconnected module is a front end for LEDA's Make_Biconnected() function. It augments a graph G to a biconnected graph G'. If G was planar, the output graph G' is also planar.

The algorithm simply uses DFS and, whenever a cut vertex is discovered, a new edge is added. Note that the number of added edges may be much higher than the number of added edges using the modules PlanAug or OptPlanAug.

General Information

Algorithm
name	Make Biconnected
long name	LEDA's Make Biconnected
author

Implementation
author	S. Näher
date
version

Pre- and Postcondition

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

#include < AGD/LEDAMakeBiconnected.h >

Creation

LEDAMakeBiconnected

A

creates an instance A of type LEDAMakeBiconnected.

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()

Implementation

The algorithm has running time $\protectO$(n + m), where n is the number of nodes and m is the number of edges of the input graph G.