PlanarColoring< UGraph > Class Template Reference
[Planarity embedding and drawing]

---

Detailed Description

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

The graph coloring problem is the coloring of the graph nodes such way that there are not adjacent nodes with the same color. The planar graphs can be always colored with four colors, it is proved by Appel and Haken and their proofs provide a quadratic time algorithm for four coloring, but it could not be used to implement 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 the 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 such way, that in each phase the node with least outgoing edges to unprocessed nodes is choosen. This order guarantees that at the time of coloring of a node it has at most five already colored adjacents. The five coloring algorithm works in the same way, but if the greedy approach fails to color with five color, ie. the node has five already different colored neighbours, it swaps the colors in one connected two colored set with the Kempe recoloring method. #include <lemon/planarity.h>

List of all members.

Public Types
typedef UGraph::template NodeMap< int >	IndexMap
	The map type for store color indexes.
typedef ComposeMap< Palette, IndexMap >	ColorMap
	The map type for store colors.
Public Member Functions
	PlanarColoring (const UGraph &ugraph)
	Constructor.
IndexMap	colorIndexMap () const
	Returns the NodeMap of color indexes.
ColorMap	colorMap () const
	Returns the NodeMap of colors.
int	colorIndex (const Node &node) const
	Returns the color index of the node.
Color	color (const Node &node) const
	Returns the color of the node.
bool	runSixColoring ()
	Calculates a coloring with at most six colors.
template<typename EmbeddingMap >
void	runFiveColoring (const EmbeddingMap &embedding)
	Calculates a coloring with at most five colors.
bool	runFiveColoring ()
	Calculates a coloring with at most five colors.

---

Constructor & Destructor Documentation

PlanarColoring

(

const UGraph &

ugraph

)

[inline]

Constructor

Precondition:

The ugraph should be simple, ie. loop and parallel edge free.

---

Member Function Documentation

IndexMap colorIndexMap

(

)

const [inline]

Returns the NodeMap of color indexes. The values are in the range [0..4] or [0..5] according to the five coloring or six coloring.

ColorMap colorMap

(

)

const [inline]

Returns the NodeMap of colors. The values are five or six distinct colors.

int colorIndex

(

const Node &

node

)

const [inline]

Returns the color index of the node. The values are in the range [0..4] or [0..5] according to the five coloring or six coloring.

Color color

(

const Node &

node

)

const [inline]

Returns the color of the node. The values are five or six distinct colors.

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 when the algorithm could color the graph with six color. If the algorithm fails, then the graph could not be planar.

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.

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, but it most cases it does not have to use Kempe recoloring method, in this case it is equivalent with the runSixColoring() algorithm.

Returns:

True when the graph is planar.