PlanarEmbedding

Declared in lemon/planarity.h, in the group Planar Embedding and Drawing; the same class on the Doxygen site.

template< typename Graph >
class PlanarEmbedding

Planar embedding of an undirected simple 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 log n ): the sort of the children of each node by their low points, made by radixSort(), takes O( n log n ) in all, and the rest O(n).

Public Types

typedef Graph::template ArcMap< Arc > EmbeddingMap

The map type for storing the embedding.

See also

embeddingMap()

Public Functions

inline PlanarEmbedding( const Graph & graph )

Constructor.

Pre:

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

inline bool run( bool kuratowski = true )

Run the algorithm.

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.

inline Arc next( const Arc & arc ) const

Give back the successor of an arc.

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

inline const EmbeddingMap & embeddingMap() const

Give back the calculated embedding map.

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.

inline bool kuratowski( const Edge & edge ) const

Give back true if the given edge is in the Kuratowski subdivision.

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

Pre:

The run() function must be called with true parameter before using this function.