Advanced Graph Theory and Combinatorics

6Planar Graphs

Roughly speaking a planar graph is a graph that one can represent (see remark 1.3) in the plane in such a way that no two edges intersect. Thus, if you think about wires connecting various electrical components, it is indeed desirable (when building a transistor, for instance) to prevent short circuits by avoiding crossings. In this chapter, orientation does not play any role. So, it is easier to think about unoriented multigraphs.

The first section is quite technical. It presents in a rigorous manner planarity that allows us to introduce the notion of a face. Then, we study the classical Euler’s formula linking the number of faces, edges and vertices in a planar graph. To make a link with Euclidean geometry, we introduce Steinitz’ theorem on convex polyhedra. Then, we color the faces of a planar graph with a minimal number of colors. Finally, Kuratowski’s theorem allows us to introduce the famous theorem of Robertson–Seymour about forbidden minors.

6.1. Formal definitions

To give precise definitions¹ of the objects we will be dealing with (mostly planar graphs, faces and dual of a graph), we need to make use of topology (so we can play with continuous maps, interior, connected components, etc.). For classical textbooks, for instance, see [ARM 83, MOH 01]. If an informal presentation is enough, then proceed directly to the next section!

A multigraph G = (V, E) can be seen as a topological space χ_G, hence we may define a continuous map from χ_G to another topological ...