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).
See also
Public Types
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:
trueif 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 PlanarEmbedding( const Graph & graph )