Eines der berühmtesten Ergebnisse der Graphentheorie ist der Vier-Farben-Satz: In jeder Landkarte (wie etwa der aus Abbildung 5.12) können die einzelnen Gebiete (Faces) mit insgesamt nur vier Farben so eingefärbt werden, dass jeweils zwei benachbarte Gebiete unterschiedliche Farben erhalten. Der Beweis dieser so einfach zu verstehenden Aussage hat sich als so schwierig herausgestellt, dass er erst 1976 vollständig und mit Hilfe eines Programmes gelang.

Wesentlich einfacher zu beweisen ist dagegen der Fünf-Farben-Satz, in dem eben fünf statt nur vier Farben zur Färbung benutzt werden dürfen; zur Fünffärbung eines Graphen ist ein effizienter und recht einfacher Algorithmus bekannt.

LEDA bietet dem entsprechend eine Funktion

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

an, die in einem planaren Graphen die Knoten (sic!) so mit den Farben (Nummern) 0 bis 4 beschriftet, dass jeweils zwei benachbarte Knoten eine unterschiedliche Farbe erhalten. Die Farben (Nummern) werden im Knoten-Array color abgelegt.

Was hat nun die Färbung von Knoten mit der Färbung von Faces in planaren Graphen zu tun? Betrachten wir dazu Abbildung 5.28. Der zu einem planar eingebetteten Graphen G duale Graph G* entsteht dadurch, dass jedem Face von G, auch dem äußeren, ein Knoten von G* entspricht; zwei Knoten in G* sind genau dann durch eine Kante verbunden, wenn die entsprechenden Faces von G benachbart sind, d. h., eine gemeinsame Kante haben.^[41]

Abbildung 5.28. Ein planarer Graph und sein dualer Graph

Jedem Face im ursprünglichen Graphen entspricht ein Knoten im dualen Graphen. Zwei Knoten im dualen Graphen haben eine gemeinsame Kante genau dann, wenn die entsprechenden Faces im ursprünglichen Graphen benachbart sind.

Eine Färbung der Knoten des dualen Graphen G* entspricht dann genau einer Färbung der Faces des ursprünglichen Graphen G. Abbildung 5.29 zeigt eine Färbung des dualen Graphen aus Abbildung 5.28 und somit eine Färbung der Faces von Abbildung 5.12

Abbildung 5.29. Eine 5-Färbung eines Graphen

Je zwei benachbarte Knoten tragen eine unterschiedliche Farbe. Insgesamt werden hier nur vier Farben benötigt. Nach dem Vier-Farben-Satz reichen vier Farben auch immer aus, aber es gibt Eingaben, bei denen die Funktion FIVE_COLOR() tatsächlich fünf Farben benötigt.

Als Beispielprogramm geben wir das Programm an, mit dem Abbildung 5.29 erzeugt wurde.

#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();
  }
}

Sowohl PLANAR() als auch FIVE_COLOR() haben Laufzeit O(n+m).

Weitere Informationen über die Funktionen aus plane_graph_alg.h finden sich auf der entsprechenden Manualseite.