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]

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

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