8   Planarity and Drawings of Graphs
We follow up with a topic which directly relates to the other important aspect of the 4 Colour Problem (Lecture 7) — with graph planarity, i.e. studying a possibility to "draw" the underlying graph (say, of the map we colour) without crossings of its edges.
Brief outline of this lecture
• Drawings of graphs, definition of a planar drawing (embedding).
• Characterization of planar graphs - the Theorem of Kuratowski.
• Colouring planar maps and graphs - the 4 Colour Problem.
• On practical graph drawing.
8.1   Drawing a graph in the plane
Definition 8.1. Planar drawing (embedding) of a graph G
is a mapping representing the vertices of G as distinct points in the plane, and the edges as simple arcs (continuous curves) joining their endvertices. Moreover, no two edges can cross each other and no edge can pass through other vertex except its ends.
A graph G is planar if there exists a planar embedding of G. c
An important example, and a source of motivation of planar graphs, are the graphs of Euclidean bodies.
Definition: The (topologically) connected areas of the plane separated by a drawing of a graph G are called the faces of this drawing (or embedding).
A planar graph can have different embeddings, with different faces. However, for 3-connected graphs the faces are uniquely determined (Corollary 8.11). □
Definition. A dual (multi)graph of a planar embedding of G is obtained by "replacing" the faces of G with dual vertices, and connecting neighbouring pairs of faces.
The dual multigraph of a planar embedding is planar again, but it may contain parallel edges and loops.
8.2   Number of faces - Euler's formula
We now introduce famous old Euler's formula for planar graphs.
Theorem 8.2. Let a planar embedding of a nonempty connected graph G have f faces. Then
\V(G)\ + f-\E(G)\ = 2.u Proof: Let the number of vertices of G be n and edges e.
• If G is a tree, i.e. G has no cycles, then its embedding has one face (cf. Jordan's curve theorem), and exactly e — n— 1 edges by Theorem 5.3. Hence n + f — e —
n+ 1 - (n- 1) = 2.u
• If G contains a cycle C, then we remove any edge of C. This decreases both the numbers of edges and of faces by one (cf. Jordan's curve theorem). The number of vertices is not changed, and so n + f — e — n + (/ — 1) — (e — 1) — 2.
The rest is finished by mathematical induction, c C
Remark: Notice that Euler's formula does not depend on a particular embedding of G. In other words, the number of faces is an invariant of a planar graph.
Corollary 8.3. A simple planar graph on n > 3 vertices has < 3n — 6 edges. A simple triangle-free planar graph on n > 3 vertices has < 2n — 4 edges, c
Proof: We can expect a connected graph G (since more edges can be added otherwise). Let G have e edges and / faces. Since G has no parallel edges, every face of G is incident with at least 3 edges, and one edge is counted at two faces. So e > \ ■ 3/, implying |e > /. From Theorem 8.2 we get
2 1
2 — n + f — e < n + -e — e — n — —e o o
e < 3(n-2) = 3n-6.n
For the other part, since G has now no triangles, every face is incident with at least 4 edges. Then e > \ ■ 4/, and |e > /. From Theorem 8.2 we get
2 1
2 — n + f — e < n + -e — e — n — — e
e < 2(n-2) = 2n-4.n
Corollary 8.4. Every simple planar graph contains a vertex of degree at most 5. Every triangle-free simple planar graph contains a vertex of degree at most 3.
8.3   Recognizing and characterizing planar graphs
Quite interestingly, planarity of graphs can be efficiently tested, even in linear time. This difficult result comes already from Tarjan, and it has been simplified several times since, but the algorithms are still not "easy".
Theorem 8.5. There exists a linear-time algorithm deciding whether an input graph is planar, c
So which graphs are not planar, for instance?
Example 8.6. We show that the graphs K$ and Kz,3 are not planar. □
K$ has 5 vertices and 10 > 3 ■ 5 — 6 edges. Kz,3 has 6 vertices and 9 > 2 ■ 6 — 4 edges, and it is triangle-free. Hence by Theorem 8.3 neither of them can be planar. □
Corollary 8.7. The graphs K$ and        are not planar.
Definition: A subdivision of a graph G is obtained by replacing some edges of G by new paths of an arbitrary positive length.
□
An important abstract description of planar graphs has been found by Kuratowski:
Theorem 8.8. A graph G is planar if and only if G contains no subdivisions of K$ or 7^33 as subgraphs, c
Question.   What are the graphs which contain no subdivisions of K33 as subgraphs?
Example 8.9. Which of the following graphs are planar? Find the planar embeddings, or prove nonplanarity of the graph(s).
The graph B, on the other hand, is not planar by Theorem 8.8 since it contains a subdivision
of ^3,3:
Uniqueness of planar embeddings
Every face of a 2-connected planar graph is enclosed by a cycle. Hence planar embeddings of 2-connected graphs can be characterized by collections of their facial cycles.a
Lemma 8.10. In any embedding of a 3-connected planar graph G, a cycle C is facial if and only if G — V(C) is a connected subgraph, c
Proof: If G' — G — V(C) is connected, then whole G' is drawn in one face of C by the Jordan curve theorem. Conversely, assume C bounds a face of G, but G' has (at least) two components X and Y. Then the "attachement" vertices of X and Y on C are not overlapping, and hence X can be separated from Y in G by removing appropriate two vertices of C, contradicting 3-connectivity of G. C
Corollary 8.11. Every two planar embeddings of a 3-connected graph are equivalent (i.e. having the same collection of facial cycles).
Moreover (without proofs) we have got:
Theorem 8.12. Isomorphism testing of planar graphs can be done in linear time, c
Theorem 8.13. Every simple planar graph has a planar embedding such that the edges are straight line segments.
8.4   Colouring maps and planar graphs
Returning to the motivation of this lecture, we survey the following important result;
- proved first by Appel and Haken in 1976,
- and then again by Robertson, Seymour, Sanders a Thomas in 1993.
Theorem 8.14. Every loopless planar graph can be properly coloured with 4 colours, a The proofs are, in both cases, very complicated, and rely on a computer search.
Easier (and weaker) cases
Hence we sketch here some simpler and weaker statements following from Corollary 8.4.
Proposition 8.15. Every loopless planar graph is ^-colourable. Every loopless triangle-free planar graph is ^-colourable.
Moreover, the following generalized result has exceptionally beautiful proof: Theorem 8.16. Every loopless planar graph has the list chromatic number at most 5.
Proof (sketch): The following is proved by a straightforward induction.
Let a planar embedded graph G have the outer face bounded by a cycle C, and all other faces be triangles. Assume every vertex ofG except those of C are assigned lists of 5 colours, some two neighbouring vertices of C have preselected distinct colours, and the rest of the vertices of C are assigned lists of 3 colours. Then there is a proper list colouring of G. [-
8.5   Practical graph drawing - Spring layout
At last we briefly look at the practical problem — how to automatically layout a "nice picture" of a given (nonplanar) graph.
One of the basic and commonly used heuristic approach is the following:
Method 8.17. Spring layout of a graph
• Create a "physical" model of the graph; the vertices being small balls which repel each other, and the edges represented by springs attracting their ends together.a
• Then iterate this model as a dynamical system until the vertex positions converge. (It is also important to suppress oscilations of the system.) □
• Even though we finally want a planar model of the graph, it is very useful to initially allow 3 dimensions (to give the model "more freedom"), and then later push all the vertices into a co-planar position.