PlanarEmbedding< UGraph > Class Template Reference
[Planarity embedding and drawing]
Detailed Description
template<typename UGraph>
class lemon::PlanarEmbedding< UGraph >
This class implements the Boyer-Myrvold algorithm for planar embedding of an undirected graph. The planar embeding is an ordering of the outgoing edges in each node, which is a possible configuration to draw the graph in the plane. If there is not such ordering then the graph contains a 
(full graph with 5 nodes) or an 
(complete bipartite graph on 3 ANode and 3 BNode) subdivision.
The current implementation calculates an embedding or an Kuratowski subdivision if the graph is not planar. The running time of the algorithm is 
. #include <lemon/planarity.h>
Public Types | |
|
typedef UGraph::template EdgeMap< Edge > | EmbeddingMap |
| The map for store of embedding. | |
Public Member Functions | |
| PlanarEmbedding (const UGraph &ugraph) | |
| Constructor. | |
| bool | run (bool kuratowski=true) |
| Runs the algorithm. | |
| Edge | next (const Edge &edge) const |
| Gives back the successor of an edge. | |
| const EmbeddingMap & | embedding () const |
| Gives back the calculated embedding map. | |
| bool | kuratowski (const UEdge &uedge) |
| Gives back true when the undirected edge is in the kuratowski subdivision. | |
Constructor & Destructor Documentation
| PlanarEmbedding | ( | const UGraph & | ugraph | ) | [inline] |
The graph should be simple, i.e. parallel and loop edge free.
Member Function Documentation
| bool run | ( | bool | kuratowski = true |
) | [inline] |
Runs the algorithm.
- Parameters:
-
kuratowski If the parameter is false, then the algorithm does not calculate the isolate Kuratowski subdivisions.
- Returns:
- True when the graph is planar.
| Edge next | ( | const Edge & | edge | ) | const [inline] |
Gives back the successor of an edge. This function makes possible to query the cyclic order of the outgoing edges from a node.
| const EmbeddingMap& embedding | ( | ) | const [inline] |
The returned map contains the successor of each edge in the graph.
| bool kuratowski | ( | const UEdge & | uedge | ) | [inline] |
Gives back true when the undirected edge is in the kuratowski subdivision
