Maximum Planar Subgraphs ( OptPlanarSubgraph )

Baseclasses

Definition

The module OptPlanarSubgraph computes a planar subgraph of an input graph G by deleting a minimum number of edges. Or in other words, the module OptPlanarSubgraph computes a maximum planar subgraph of an input graph G ([JM96,Mut94]).

Since this problem is an NP-hard optimization problem, the algorithm may take exponential time. On average, instances with around 60 edges can be solved to provable optimality within a few minutes.

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 maximum planar subgraph problem the mathematical investigation has been done in the articles by Jünger and Mutzel [JM96] and Mutzel [Mut94].

General Information

Algorithm
name	Maximum Planar Subgraph
long name	Maximum Planar Subgraph
author	P. Mutzel

Implementation
author	S. Fialko
date	March 1998
version

Pre- and Postcondition

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

#include < AGD/OptPlanarSubgraph.h >

Creation

OptPlanarSubgraph

S

creates an instance S of type OptPlanarSubgraph.

Operations

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

bool	S.check(const graph& G, AgdKey& p)
bool	S.call(const graph& G, list<edge>& L)
bool	S.call(graph& G)
bool	S.call(GraphCopy& G, list<edge>& L)
int	S.num_del_edges()