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 K₅ (full graph with 5 nodes) or a K_3,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.

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 EmbeddingMap &	embeddingMap () 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

kuratowski

If 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.