Next: Edge Re-Insertion Up: Planarization Previous: Planarization Modules ( PlanarizerModule Contents Index

Planarization with Planar Subgraph ( SubgraphPlanarizer )

Baseclasses

$\begin{picture}(7,4) \thicklines \put(0,3){\framebox (5.5,1){\bf AGDModule}}... ...0,-1){1}}\put(2.3,0){\framebox (6.2,1){\bf SubgraphPlanarizer}} \end{picture}$

Definition

The class SubgraphPlanarizer represents a general framework for planarization using planar subgraphs. It first transforms a general graph into a planar graph (using a subgraph planarization module) by deleting a set of edges and then reinserting the edges so that the number of crossings is small. Finally, the crossings are substituted by artificial crossing vertices so that the resulting graph is planar. The planarization algorithms and the reinsertion algorithms are exchangeable modules allowing to use SubgraphPlanarizer with different methods for planarization and edge-reinsertion.

General Information

Algorithm

name Subgraph Planarizer

long name Planarization with Planar Subgraph

author

Implementation

author C. Gutwenger

date August 1997

version

Pre- and Postcondition

precondition = {simple, noselfloops}

postcondition(PRE) = {planar, simple, noselfloops}

Exchangeable Modules Instances of type SubgraphPlanarizer provide the following module options:

$\bullet$

subgraph
a SubgraphModule option used to compute a planar subgraph of the input graph.

guaranteed precondition: {simple, noselfloops, noreversals}

required postcondition: {planar, simple, noselfloops, noreversals}

initial module: PlanarSubgraph

$\bullet$

inserter
an EdgeInsertionModule option used to reinsert the deleted edges.

guaranteed precondition: $\emptyset$

required postcondition: $\emptyset$

initial module: ShortestPathInserter

#include < AGD/SubgraphPlanarizer.h >

Creation

SubgraphPlanarizer P creates an instance P of type SubgraphPlanarizer.

Operations

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

bool P.check(const GraphCopy& G, AgdKey& p)

bool P.call(GraphCopy& G, edge_array<list<edge> >& chain)

Access to Options

bool P.set_subgraph(const SubgraphModule& M)

bool P.set_inserter(const EdgeInsertionModule& M)

int P.insertedEdges()

float P.timeSubgraph()

float P.timeInsertion()

Next: Edge Re-Insertion Up: Planarization Previous: Planarization Modules ( PlanarizerModule Contents Index

Algorithm
name	Subgraph Planarizer
long name	Planarization with Planar Subgraph
author

Implementation
author	C. Gutwenger
date	August 1997
version

precondition	=	{simple, noselfloops}
postcondition(PRE)	=	{planar, simple, noselfloops}

guaranteed precondition:	{simple, noselfloops, noreversals}
required postcondition:	{planar, simple, noselfloops, noreversals}
initial module:	PlanarSubgraph

guaranteed precondition:	$\emptyset$
required postcondition:	$\emptyset$
initial module:	ShortestPathInserter

bool	P.check(const GraphCopy& G, AgdKey& p)
bool	P.call(GraphCopy& G, edge_array<list<edge> >& chain)

bool	P.set_subgraph(const SubgraphModule& M)
bool	P.set_inserter(const EdgeInsertionModule& M)
int	P.insertedEdges()
float	P.timeSubgraph()
float	P.timeInsertion()