C-Planarity Embedding ( CPlanarEmbed )

Baseclasses

Definition

The class CPlanarEmbed represents the c-planarity testing and embedding algorithm by Q.-W. Feng. It tests if a cluster graph CG is c-connected and c-planar and embeds CG c-planar.

General Information

Algorithm
name	C-Planar Embedding
long name	C-Planar Embedding
author	Q.-W. Feng

Implementation
author	C. Liebel, C. Buchheim
date	August 1999
version

Pre- and Postcondition

precondition

=

$\emptyset$

#include < AGD/CPlanarEmbed.h >

Creation

CPlanarEmbed

PE

creates an instance PE of type CPlanarEmbed.

Operations

bool	PE.is_cplanar(const ClusterGraph& CG)
		returns true iff CG is c-connected and c-planar.
bool	PE.call(ClusterGraph& CG)	calls PE for cluster graph CG. If CG is c-connected and c-planar, CG is turned into a map, embedded c-planar, and true is returned. Otherwise, false is returned.
bool	PE.call(ClusterGraph& CG, leda_list<leda_edge>& L)
		calls PE for cluster graph CG. If CG is c-connected and c-planar, CG is turned into a map by adding the edges returned in L, embedded c-planar, and true is returned. Otherwise, false is returned.

Implementation

The running time of is_cplanar() and call() is $\protectO$(n²), where n is the number of vertices in CG.