Loading...
Searching...
No Matches
PlanarEmbedding< Graph > Class Template Reference
Algorithms » Planar Embedding and Drawing

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

## 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

## EmbeddingMap

template<typename Graph>

typedef Graph::template ArcMap<Arc> EmbeddingMap

The map type for storing the embedding.

See also
  embeddingMap()

## Constructor & Destructor Documentation

## PlanarEmbedding()

template<typename Graph>

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

## run()

template<typename Graph>

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.

## next()

template<typename Graph>

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.

## embeddingMap()

template<typename Graph>

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.

## kuratowski()

template<typename Graph>

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.