Learning objectives
Planar graphs and planar embeddings 
Bidirected graphs and maps 
Face cycles and faces 
Order preserving embeddings and planar maps 
The functions Is_Plane_Map() and PLANAR() 
Graphs serve for recording relationships between objects. To store graphs in a computer, it suffices to store the combinatorial structure of the nodes and edges, for example, in adjacency lists. We, however, being humans, prefer drawings that quickly provide us with an overlook over a graph. Therefore drawing graphs is a big issue. We shall deal here with drawings that are made on a sheet of paper, that is, drawings in the twodimensional plane (sometimes graphs are drawn onto a sphere or a torus, as the borderlines on a globe, for example; this kind of drawings shall not be of further interest here).
Of course, there are infinitely many ways to draw a graph onto a sheet of paper (to be more precise, into the twodimensional 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 nonplanar 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.)
A very famous result from graph theory is the theorem stating that a graph is nonplanar 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.
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:
reversal(e)=(w,v), that is, the reversal edge of e indeed is reversely directed, so reversal() deserves its name.
reversal(reversal(e))=e, that is, also in the presence of multiedges always two edges correspond to one another.
e is different from reversal(e), that is, also in the presence of selfloops each selfloop edge has a different selfloop edge as its reversal edge.
Each edge e occurs as the reversal edge reversal(e') of a different edge e', that is, the mapping is bijective.
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.
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.
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_{0} 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:
face_cycle_succ(j) = cyclic_adj_pred(reversal(j))
= cyclic_adj_pred(i) = c,
face_cycle_succ(c) = cyclic_adj_pred(reversal(c))
= cyclic_adj_pred(d) = b.
face_cycle_succ(b) = cyclic_adj_pred(reversal(b))
= cyclic_adj_pred(a) = e.
face_cycle_succ(e) = cyclic_adj_pred(reversal(e))
= cyclic_adj_pred(f) = j.
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.
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 editandrun 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 selfloops. 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.
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

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:
Although the graph depicted in Figure 5.16 is planarly embedded,
this embedding does not correspond to the planar map
computed by PLANAR()
, that is, there
is a different embedding (that is, a different way to draw
the graph into the plane) in which the face cycles are
drawn in the “correct” circular direction,
even if this embedding may look completely different from
the original one.
Figure 5.17 shows such an embedding of the Saarland graph, which looks completely different from the original embedding, in which, however, each face cycle from Figure 5.16 indeed corresponds to one face of the embedding.
The graph has a another plane map in which the face
cycles correspond to the faces of the embedding, which,
unfortunately and by chance, are not computed by a call of
PLANAR()
, though.
This is the case in Figure 5.16. Such a map can easily be created from the map depicted there by reversing the directions of all edges.