All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
List of all members | 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>

Public Types

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

Public Member Functions

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

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.