Naive Maximal Planar Subgraphs ( NaiveMaximalPlanarSubgraph )

Baseclasses

Definition

The module NaiveMaximalPlanarSubgraph computes a maximal planar subgraph of an input graph G by the following simple strategy: We start with the empty graph and construct a maximal planar subgraph by trying to add the edges of G one after the other in an arbitrary order. For each edge we use a planarity testing algorithm to check if the current subgraph becomes non-planar after adding the edge. If the resulting graph is still planar, the edge is added, otherwise, the edge is discarded.

General Information

Algorithm
name	Naive Maximal Planar Subgraph
long name	Naive Maximal Planar Subgraph
author

Implementation
author	T. Ziegler
date	July 2000
version

Pre- and Postcondition

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

Optional Parameters Instances of NaiveMaximalPlanarSubgraph provide the following optional parameters:

$\bullet$

int runs = 3
It is not difficult to see that the result of the algorithm depends on the order in which the edges are considered. The parameter determines, how many different insertion orders are tested. The insertion orders are obtained by randomly permuting the list of all edges of the given graph. The result is the largest computed maximal planar subgraph.

#include < AGD/NaiveMaximalPlanarSubgraph.h >

Creation

NaiveMaximalPlanarSubgraph

S

creates an instance S of type NaiveMaximalPlanarSubgraph.

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$(m(n + m)), where n is the number of nodes and m is the number of edges of the input graph G.