Planar Subgraphs ( PlanarSubgraph )

Baseclasses

Definition

The module PlanarSubgraph computes a planar subgraph of an input graph G by deleting (in general, a small number of) edges using PQ-trees [Lei95,JLM96]. The algorithm is similar to the one by Jayakumar et al. [JTS89]. Notice that planarization algorithms using PQ-trees cannot guarantee to delete a minimum nor a minimal number of edges [JLM98,JLM97]. However, among the classical heuristics for the maximum planar subgraph problem, this is one of the best [Mut94].

The idea of the algorithm is essentially to proceed as in the planarity testing algorithm based on PQ-trees. First, an st-numbering is constructed and then vertices are subsequently added to the empty graph. Together with the newly constructed graph, a so-called bush form T (represented as a PQ-tree) is updated. In order to add a new vertex v without introducing crossings, all the virtual edges labeled v in T need to be brought together. If this fails, some of the edges corresponding to those virtual edges are deleted.

General Information

Algorithm
name	Planar Subgraph
long name	Planar Subgraph
author	R. Jayakumar et al., S. Leipert

Implementation
author	S. Leipert
date	November 1997
version

Pre- and Postcondition

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

Optional Parameters Instances of PlanarSubgraph provide the following optional parameters:

$\bullet$

int runs = 3
determines, how many times the actual planar subgraph algorithm is called. Each repetition (except for the first) starts with randomly permuted node lists. Deterministic behaviour can be achieved by setting runs to 1.

#include < AGD/PlanarSubgraph.h >

Creation

PlanarSubgraph

S

creates an instance S of type PlanarSubgraph.

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

Access to Options

int	S.runs()
void	S.runs(int n)

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.