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>

List of all members.

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.