Public Types | Public Member Functions

PlanarEmbedding< Graph > Class Template Reference


Detailed Description

template<typename Graph>
class lemon::PlanarEmbedding< Graph >

This class implements the Boyer-Myrvold algorithm for planar embedding of an undirected simple graph. The planar embedding is an ordering of the outgoing edges of the nodes, which is a possible configuration to draw the graph in the plane. If there is not such ordering then the graph contains a K5 (full graph with 5 nodes) or a K3,3 (complete bipartite graph on 3 Red and 3 Blue nodes) subdivision.

The current implementation calculates either an embedding or a Kuratowski subdivision. The running time of the algorithm is O(n).

See also:
PlanarDrawing, checkPlanarity()

#include <lemon/planarity.h>

List of all members.

Public Types

typedef Graph::template ArcMap
< Arc > 
EmbeddingMap
 The map type for storing the embedding.

Public Member Functions

 PlanarEmbedding (const Graph &graph)
 Constructor.
bool run (bool kuratowski=true)
 Run the algorithm.
Arc next (const Arc &arc) const
 Give back the successor of an arc.
const EmbeddingMapembeddingMap () const
 Give back the calculated embedding map.
bool kuratowski (const Edge &edge) const
 Give back true if the given edge is in the Kuratowski subdivision.

Member Typedef Documentation

typedef Graph::template ArcMap<Arc> EmbeddingMap

The map type for storing the embedding.

See also:
embeddingMap()

Constructor & Destructor Documentation

PlanarEmbedding ( const Graph &  graph) [inline]

Constructor.

Precondition:
The graph must be simple, i.e. it should not contain parallel or loop arcs.

Member Function Documentation

bool run ( bool  kuratowski = true) [inline]

This function runs the algorithm.

Parameters:
kuratowskiIf this parameter is set to false, then the algorithm does not compute a Kuratowski subdivision.
Returns:
true if the graph is planar.
Arc next ( const Arc &  arc) const [inline]

This function gives back the successor of an arc. It makes possible to query the cyclic order of the outgoing arcs from a node.

const EmbeddingMap& embeddingMap ( ) const [inline]

This function gives back the calculated embedding map, which contains the successor of each arc in the cyclic order of the outgoing arcs of its source node.

bool kuratowski ( const Edge &  edge) const [inline]

This function gives back true if the given edge is in the found Kuratowski subdivision.

Precondition:
The run() function must be called with true parameter before using this function.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines