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

## Detailed Description

template<typename Graph>
class lemon::PlanarColoring< Graph >

The graph coloring problem is the coloring of the graph nodes so that there are no adjacent nodes with the same color. The planar graphs can always be colored with four colors, which is proved by Appel and Haken. Their proofs provide a quadratic time algorithm for four coloring, but it could not be used to implement an efficient algorithm. The five and six coloring can be made in linear time, but in this class, the five coloring has quadratic worst case time complexity. The two coloring (if possible) is solvable with a graph search algorithm and it is implemented in bipartitePartitions() function in LEMON. To decide whether a planar graph is three colorable is NP-complete.

This class contains member functions for calculate colorings with five and six colors. The six coloring algorithm is a simple greedy coloring on the backward minimum outgoing order of nodes. This order can be computed by selecting the node with least outgoing arcs to unprocessed nodes in each phase. This order guarantees that when a node is chosen for coloring it has at most five already colored adjacents. The five coloring algorithm use the same method, but if the greedy approach fails to color with five colors, i.e. the node has five already different colored neighbours, it swaps the colors in one of the connected two colored sets with the Kempe recoloring method.

`#include <lemon/planarity.h>`

## Public Types

typedef Graph::template NodeMap< int > | IndexMap
| The map type for storing color indices.
typedef ComposeMap< Palette, IndexMap > | ColorMap
| The map type for storing colors.

## Public Member Functions

| PlanarColoring (const Graph &graph)
| Constructor.
IndexMap | colorIndexMap () const
| Return the node map of color indices.
ColorMap | colorMap () const
| Return the node map of colors.
int | colorIndex (const Node &node) const
| Return the color index of the node.
Color | color (const Node &node) const
| Return the color of the node.
bool | runSixColoring ()
| Calculate a coloring with at most six colors.
template<typename EmbeddingMap>
void | runFiveColoring (const EmbeddingMap &embedding)
| Calculate a coloring with at most five colors.
bool | runFiveColoring ()
| Calculate a coloring with at most five colors.

## Member Typedef Documentation

## ColorMap

template<typename Graph>

typedef ComposeMap<Palette, IndexMap> ColorMap

The map type for storing colors.

See also
  Palette, Color

## Constructor & Destructor Documentation

## PlanarColoring()

template<typename Graph>

PlanarColoring | ( | const Graph & | graph | ) |

inline

Constructor.

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

## Member Function Documentation

## colorIndexMap()

template<typename Graph>

IndexMap colorIndexMap | ( |  | ) | const

inline

This function returns the node map of color indices. The values are in the range ``[0..4] or ``[0..5] according to the coloring method.

## colorMap()

template<typename Graph>

ColorMap colorMap | ( |  | ) | const

inline

This function returns the node map of colors. The values are among five or six distinct colors.

## colorIndex()

template<typename Graph>

int colorIndex | ( | const Node & | node | ) | const

inline

This function returns the color index of the given node. The value is in the range ``[0..4] or ``[0..5] according to the coloring method.

## color()

template<typename Graph>

Color color | ( | const Node & | node | ) | const

inline

This function returns the color of the given node. The value is among five or six distinct colors.

## runSixColoring()

template<typename Graph>

bool runSixColoring | ( |  | ) |

inline

This function calculates a coloring with at most six colors. The time complexity of this variant is linear in the size of the graph.

Returns
  `true` if the algorithm could color the graph with six colors. If the algorithm fails, then the graph is not planar.

Note
  This function can return `true` if the graph is not planar, but it can be colored with at most six colors.

## runFiveColoring() [1/2]

template<typename Graph>
template<typename EmbeddingMap>

void runFiveColoring | ( | const EmbeddingMap & | embedding | ) |

inline

This function calculates a coloring with at most five colors. The worst case time complexity of this variant is quadratic in the size of the graph.

Parameters

  embedding | This map should contain a valid combinatorical embedding, i.e. a valid cyclic order of the arcs. It can be computed using PlanarEmbedding.

## runFiveColoring() [2/2]

template<typename Graph>

bool runFiveColoring | ( |  | ) |

inline

This function calculates a coloring with at most five colors. The worst case time complexity of this variant is quadratic in the size of the graph.

Returns
  `true` if the graph is planar.