Of course, there are infinitely many ways to draw a graph onto a sheet of paper (to be more precise, into the two-dimensional plane). Of all these, the drawings in which the edges do not cross are of primary interest, just because they are least confusing for the eye. Such a drawing is called a planar embedding. A graph is called planar if it has a planar embedding. By far not all graphs are planar. For example, the minimal non-planar graphs are the ones depicted in Figure 5.11. The left one is the complete graph of degree 5, which is denoted as K5; the right one is the complete bipartite graph with 3 nodes in each subset, which is denoted as K3,3. (A graph is called bipartite if the nodes can be decomposed into two subsets A and B such that for each edge the source and the target node are contained in a different subset.)

Figure 5.11. The non-planar Kuratowski graphs K5 and K3,3

The minimal non-planar graphs. A graph is non-planar if and only if it contains a subdivision of K5 or K3,3.

A very famous result from graph theory is the theorem stating that a graph is non-planar if and only if it contains a subdivision of K5 or K3,3 as a subgraph. A subdivision of a graph arises by subdividing edges. Subdividing an edge means to split it into two edges by inserting a new node somewhere on the edge so that the old edge is replaced by two new edges. The Polish mathematician Kazimierz Kuratowski was the first one to prove this theorem; in his honor, the two graphs from Figure 5.11 are called Kuratowski graphs, too.

This section explains LEDA's view of planarly embedded graphs and of the concepts related thereto.

In daily life, we often encounter maps such as the one from Figure 5.12. These maps show a polygonal net in the plane, that is, the edges of a planarly embedded graph form a (finite) set of adjacent polygons. Each of these polygons stands for a country or a face on the map. The map from Figure 5.12 represents the home country of LEDA, the beautiful Saarland. It shows 7 faces: the 6 districts of the Saarland and the “rest of the world”. This rest of the world is also considered a face, the outer face.

Figure 5.12. The Saarland as a graph

The Saarland consists of 6 faces (districts). The outer face contains everything not belonging to the Saarland. So this map shows 7 faces. The graph is planarly embedded; therefore it is planar. There are many different ways to draw the graph, among them many that are not planar embeddings!

What is LEDA's view of such maps? How are they coded? By different reasons that we do not want to dwell on here, the data structure of choice is a bidirected graph in which each edge knows a corresponding reverse edge. We extend our previous definition of a bidirected graph to the following one:

A directed graph is called bidirected if the there is a mapping reversal() that maps each edge e=(v,w) to a reversal edge (denoted as reversal(e)) such that the following holds:

How do we create such a bidirected graph now? Of course, for each edge we may explicitly insert the corresponding reversal edge; it is much easier, however, to insert only one edge of each pair and to call

G.make_bidirected();

then. This method inserts a minimal number of edges to G to make it bidirected.

Whether a graph is bidirected may be tested with

G.is_bidirected();

Figure 5.13 shows the graph from Figure 5.12 as a bidirected graph. The meaning of the numbers attached to the edges will soon become clear.

Figure 5.13. The Saarland as a bidirected graph.

Edges with the same numbering belong to the same face cycle.

LEDA's coding of a planarly embedded graph comprises even more: Each edge has to know its (unique) reversal edge. Such a graph is called a map. Figure 5.14 shows such a map.

Figure 5.14. A map

The following pairs of edges are reversal to one another: a and b, c and d, e and f, g and h, i and j. The relationships reversal(g)=j and reversal(h)=i would also be conceivable. For example, let adj_edges(0)=(h,j,f), adj_edges(1)=(g,c,i), and adj_edges(2)=(e,a,b,d). Then there are the face cycles [h,i], [j,c,b,e], [f,d,g], and [a].

To yield a bidirected graph from a map, the reversal edge has to be set for each edge e. There are two ways to do this: The first one is to turn a bidirected graph into a map with a call of

G.make_map();

This method returns false if the graph is not bidirected. It preserves reversal edge relationships already set, that is, if f=reversal(e) holds before the call, then so it does after.

The second way is to set the reversal edge f=reversal(e) explicitly for each edge e by hand. This may be achieved by a call of

G.set_reversal(e,f);

which defines f as the reversal edge of e, as well as, vice versa, e as the reversal edge of f. This method first tests whether the two edges are reversal to one another, and does nothing if it they are not. If the reversal edge e'=reversal(e) of e has already been set before, the reversal edge of e' is set to nil. The same holds for an already set reversal edge of f.

There is a last building block missing to completely understand LEDA's view of planarly embedded graphs. Eventually, concerning a planar embedding, we want to able to say something like “Face X is exactly the face that is bordered by the following edges: ...” and then to traverse these edges in the corresponding order. The faces of an embedding are also denoted as faces. They result from certain (adjacent) edges being traversed in a certain order (a cycle); each face contains everything that, in an intuitive sense, lies “to the left of all edges” of the cycle. So let us first define the term “face cycle”:

The nodes that leave a node v are contained in its adjacency list adj_edges(v); since this internally is a circular list, these nodes are contained in a certain order therein. Therefore, for each edge e we are able to determine the cyclic successor and the cyclic predecessor in the list adj_edges(source(e)). For an edge e

G.cyclic_adj_succ(e);
G.cyclic_adj_pred(e);

return this successor and predecessor, respectively, in the cyclic adjacency list of source(e). We shall define now the face cycle successor and the face cycle predecessor as

G.face_cycle_succ(e) == G.cyclic_adj_pred(G.reversal(e));
G.face_cycle_pred(e) == G.cyclic_adj_succ(G.reversal(e));

Of course, this definition is valid only in a map G, because only there the information G.reversal(e) is always present.

A face cycle arises by starting from an edge e=e₀ and successively moving to each next face cycle successor e_i+1=face_cycle_succ(e_i). Without proof, we want to state that, moving in this way, we shall always come back to the edge e, that e is the first edge to appear twice in the edge sequence created in this way, and that each edge of the map is contained in exactly one face cycle (see Exercise 59). So the face cycles divide the edge set E of a graph into disjoint subsets.

To give an example, we assume in Figure 5.14 that the order of the edges in the adjacency lists reads as follows: adj_edges(0)=(h,j,f), adj_edges(1)=(g,c,i), and adj_edges(2)=(e,a,b,d). Then the face cycle that edge j is contained in results as follows:

This yields the face cycle [j,c,b,e]. The other face cycles [h,i], [f,d,g], and [a] result correspondingly.

	Important
	Face cycles are first of all purely combinatorial structures that depend on the order of the edges in the adjacency lists. In general, different orders in the adjacency lists yield different face cycles. A face cycle does not always correspond to a face of an embedded graph!

This statement is confirmed by Figure 5.15. There all edges that are contained in the same face cycle are labeled with the same number. Obviously the face cycle with number 4 is not a face of the graph if the latter one is regarded as embedded into the plane. The same holds for the face cycle with number 1 from Figure 5.13.

Figure 5.15. Maps and face cycles

To describe LEDA's interface to maps and face cycles we present a program that allows the user to input a graph interactively and to make visible the face cycles therein: Edges belonging to the same face cycle are labeled with the same number and are drawn with the same color. Figure 5.15 has been designed with it. The program additionally broadens our knowledge of the interface of GraphWin. The reader may play around with this program until he has developed an intuitive understanding of face cycles!

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

using leda::graph;
using leda::face;
using leda::edge;
using leda::GraphWin;
using leda::window;
using leda::color;
using leda::string;
using std::cout;


int main()
{
  graph G;

  GraphWin gw(G, 500, 500, "Maps and Face Cycles");
  gw.set_edge_label_type(leda::user_label);
  gw.set_edge_label_pos(leda::west_pos);
  gw.set_flush(false);
  gw.display(window::center,window::center);

  while(gw.edit()) { 

    G.make_bidirected();
    G.make_map();
    G.compute_faces();

    gw.update_graph();

    int num_face = 0;
    face f;
    forall_faces(f,G) {
      num_face++;
      edge e;
      forall_face_edges(e,f) {
        gw.set_color(e, color(num_face % 16));
        gw.set_label_color(e, color(num_face % 16));
        gw.set_user_label(e, string("%d",num_face));
      }
    }
   
    gw.redraw();
  }
}

In every edit-and-run cycle, we make the graph G, which has been edited by the user, bidirected, and then use it to construct a map. (So the user does not have to input reverse edges; anyway, a GraphWin does not allow to set the reversal edge relationships.)

A call of

G.compute_faces();

computes the face cycles of G from this map.

These face cycles can be iterated over with the macro

forall_faces(f,G) { ... }

The corresponding data type of LEDA is called face.

Each face cycle f consists of edges. These edges can be iterated over with the macro

forall_face_edges(e,f) { ... }

So by nesting both macros, all face cycles can be traversed edge by edge.

After the modifications that we perform on the underlying graph G outside of edit(), it is mandatory here to tell the GraphWin by update_graph() to adapt its internal structures. If we happen to forget this, the program may crash!

For labeling the edges, we set the attribute user_label; for coloring them, we use the attribute label_color. But first we have to tell the GraphWin that we want to use the user defined label for labeling and where it is to appear; we do this with

gw.set_edge_label_type(leda::user_label);
gw.set_edge_label_pos(leda::west_pos);

Since the graph is not to be redrawn after every labeling and coloring operation, we first set the flush parameter to false and redraw everything at the end of the loop with redraw().

We shall come now to the point that we have aimed at in this whole section: planarly embedded graphs and LEDA's view of them. Under which preconditions are we able to draw a graph into the plane such that none of its edges cross, and how can we access the individual faces then? We already said above that maps are the data structure of choice for planarly embedded graphs.

If in a planar embedding of a map, that is, in a drawing of it in which no edges cross, for each node v the order of the edges around v (counterclockwise) is the same as the order of the edges in the adjacency list adj_edges(v), then this embedding is called an order preserving embedding. The embedding of the map from Figure 5.14 is not order preserving, because, for example, the order h, f, j of the edges around node 0 is not the same as the order h, j, f in the adjacency list adj_edges(0). In an order preserving embedding of a map, the face cycles of the map always correspond exactly to the faces of the embedding.

A map is called plane if it has an order preserving, planar embedding. The map from Figure 5.14 is plane; only the order of the edges in the adjacency lists has to be modified such that it is the same as the order in the embedding. There are certainly maps that are not plane, though. A call of

G.Is_Plane_Map();

tests whether G is a plane map. The header file that has to be included is graph_misc.h.

In general, however, this is not what we want. In most cases, we rather want to decide whether a given graph G is planar, and if it is, we want to have a planar embedding of it drawn. We will discuss graph drawing not until Section 5.3.8. Whether a graph is planar at all can be tested with

PLANAR(G, embed);

Here G must not have self-loops. The header file that has to be included is plane_graph_alg.h. The default argument embed is set to false; if it is passed as true and if G indeed is planar, PLANAR() additionally reorders the edges in the adjacency lists such that G becomes a plane map. This means that the edges around the nodes now are ordered in such a way that they correspond to the ordering in a drawing in which they do not cross. Moreover, it means that the face cycles of the map obtained in this way correspond to the faces of a planar embedding.

The following program does nearly the same as the program before. It additionally tests whether the graph that has been input by the user is planar, and if it is so, it computes a planar map from it. This does not mean, however, that it computes a planar embedding of the graph. It rather makes visible the face cycles of a possible planar embedding.

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

using leda::graph;
using leda::face;
using leda::edge;
using leda::GraphWin;
using leda::window;
using leda::color;
using leda::string;
using std::cout;


int main()
{
  graph G;

  GraphWin gw(G, 500, 500, "Planarity Testing");
  gw.set_edge_label_type(leda::user_label);
  gw.set_edge_label_pos(leda::west_pos);
  gw.set_flush(false);
  gw.display(window::center,window::center);

  while(gw.edit()) { 

    G.make_bidirected();
    G.make_map();
    gw.update_graph();

    bool is_planar = PLANAR(G, true);

    G.compute_faces();

    int num_face = 0;
    face f;
    forall_faces(f,G) {
        num_face++;
        edge e;
        forall_face_edges(e,f) {
          gw.set_color(e, color(num_face % 16));
          gw.set_label_color(e, color(num_face % 16));
          gw.set_user_label(e, string("%d",num_face));
        }
    }
    gw.redraw();

    if(is_planar) 
      gw.message("This Graph is planar. Click <done> to continue.");
    else
      gw.message("This Graph is not planar. Click <done> to continue.");

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

Figure 5.16 shows the output of this program for the original map from Figure 5.13. Both maps differ in the ordering of their adjacency lists; this yields different face cycles.

Figure 5.16. The Saarland as a planar map

The graph is planar. The program has computed a planar map and made visible the face cycles. They do not correspond to the faces of the planar embedding shown, though. For example, the edges of the cycle with number 3 are drawn clockwise; the face bordered by theses edges would therefore lie “outside” of the cycle.

Anyhow, neither here the face cycles correspond to the face cycles of the depicted planar embedding of the graph. After all, we had only stated that our program makes visible the face cycles of a possible planar embedding.

	Warning
	If one starts from a planarly drawn graph and has PLANAR() compute a planar map, it may well be that the face cycles of the computed map do not correspond to the faces of the original drawing.

How is this possible? We had already mentioned before that a face comprises everything that is located to the left of all edges of the surrounding face cycle. So the edges of the face cycle belonging to the planar embedding of the face have to be ordered counterclockwise - with the exception of the edges of the outer face, which are ordered clockwise.

In Figure 5.16, however, the edges of the face cycle with number 3, for example, are ordered clockwise. Therefore these face cycles cannot correspond to the faces of the planar embedding shown.

But LEDA's function PLANAR() proudly claims to compute a planar map if the graph is planar! How does this fit together? Well, there are two possible explanations:

Figure 5.17. A plane map of the Saarland that complies with a planar embedding

Each face cycle corresponds to a face of the planar embedding. The face cycle 1 corresponds to the outer face, that is, to the rest of the world. The map is the same as the one from Figure 5.16. Unfortunately, the embedding does not look at all like the Saarland any more.

make_bidirected(), make_map(), and compute_faces() take a running time of 0(n+m).