A very famous result in graph theory is the Four Color Theorem: In every map (such as the one from Figure 5.12), the individual faces can be colored with only four colors altogether such that each two adjacent faces receive different colors. The proof of this statement, which is so easy to understand, has turned out to be so difficult that it could be completely finished not until 1976, and only with the help of a program.

In contrast, the Five Color Theorem, in which five instead of only four colors may be used, is much more easy to prove; an efficient and quite simple algorithm for five-coloring a graph is known.

Accordingly, LEDA offers a function

void FIVE_COLOR(graph& G, node_array<int>& color);

that labels the nodes (sic!) in a planar graph with the numbers 0 to 4 such that each two adjacent nodes receive a different number (color). The colors are stored in the node array color.

What does coloring nodes have to do with coloring faces in planar graphs? Let us have a look at Figure 5.28. The dual graph G* of a planarly embedded graph G arises by creating one node in G* for each face of G, also for the outer face; two nodes in G* are connected by an edge if and only if the corresponding faces of G are adjacent, that is, if they have an edge in common. ^[42]

Figure 5.28. A planar graph and its dual graph

A node in the dual graph corresponds to each face in the original graph. Two nodes in the dual graph have an edge in common if and only if the corresponding faces in the original graph are adjacent.

A coloring of the nodes of the dual graph G* then corresponds exactly to a coloring of the faces of the original graph G. Figure 5.29 shows a coloring of the dual graph from Figure 5.28 and therefore a coloring of the faces from Figure 5.12

Figure 5.29. A five-coloring of a graph

Each two adjacent nodes have a different color. A total of only four colors are used here. According to the Four Color Theorem, four colors always suffice, but there are inputs on which the function FIVE_COLOR() indeed needs five colors.

As an example program, we list the program that has been used to create Figure 5.29.

#include <LEDA/graph.h>
#include <LEDA/graphwin.h>
#include <LEDA/plane_graph_alg.h>
#include <LEDA/node_array.h>
#include <LEDA/color.h>
#include <LEDA/string.h>

using leda::graph;
using leda::node;
using leda::node_array;
using leda::GraphWin;
using leda::window;
using leda::color;
using leda::string;

int main()
{
  graph G;

  GraphWin gw(G, 500, 500, "Five Coloring");
  gw.set_node_label_type(leda::user_label);
  gw.set_edge_direction(leda::undirected_edge);
  gw.set_flush(false);
  gw.display(window::center,window::center);

  while(gw.edit()) { 

    node_array<int> five_color(G);

    if(PLANAR(G, false)) {
      FIVE_COLOR(G, five_color);
      node v;
      int max_color = 0;
      forall_nodes(v,G) {
        gw.set_color(v, color(five_color[v]));
        if(max_color < five_color[v])
          max_color = five_color[v];
        gw.set_user_label(v, string("%ld",five_color[v]));
      }
      gw.message( string("%ld", max_color + 1) + " colors used "
                 + "to color this graph. Click <done>.");
    }
    else {
      gw.message("This Graph is not planar. Click <done> to continue.");
    }
    gw.redraw();

    gw.wait(); // waits until done is pressed
    gw.del_message(); 
    gw.redraw();
  }
}

Both PLANAR() and FIVE_COLOR() have a running time of O(n+m).

Further information about the functions from plane_graph_alg.h can be found on the corresponding manual page.