5.3.7. Algorithms for planar graphs

Learning objectives

Algorithms from plane_graph_alg.h
Coloring problems
Node coloring with FIVE_COLOR()
Dual graphs

The header file plane_graph_alg.h declares functions that test graphs for planarity or run algorithms on planar graphs. In Section 5.2.6, we already came to know PLANAR(), which is one of these functions; it tests whether a (directed) graph is planar and, if it is, turns it into a planar map.

Coloring problems and dual graphs

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 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

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.

Filename: FiveColoring.C
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
#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();
  }
}

Running times and further information

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.

Exercises

Exercise 68.

Find a graph for which FIVE_COLOR() indeed needs five colors for coloring.

Exercise 69.

The function PLANAR() is available also with the following signature:

bool PLANAR(graph& G, list<edge>& k_subdiv, bool embed = false);

In case G is not planar, it returns a subdivision of the Kuratowski graph K5 or K3,3 in k_subdiv. Create a non-planar graph G and use this function to make visible such a subdivision, which, as we discussed in Section 5.2.6, is a proof for the non-planarity of G.



[42] In an extended definition, G* has an edge for every common edge of two faces F1 and F2 of G. So multiedges may occur in this definition, which does not modify the problem definition, though.




Imprint-Dataprotection