8    Graph Planarity, and Drawings of Graphs
We continue with a topic which directly relates to the other important aspect of the 4 colour problem (Lecture 7) - graph planarity, i.e. the possibility to "draw" the underlying graph (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.
•   Drawing with edge crossings, and the crossing number of a graph.
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.
etr Hliněný,   Fl MU Br
Fl: MAOIO:  Planarity and drawings
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). c
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.
etr Hliněný,   Fl MU Brno                                                                                Fl: MAOIO:  Planarity and drawings
r
We now introduce famous 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.n
Proof:  Let the number of vertices of G be v and edges h.
•   If G is a tree, i.e. G has no cycles, then its embedding has one face, and exactly h = v — 1 edges by Theorem 4.3. Hence v + f — h = v + í — (v — 1) = 2.d
•   If G contains a cycle C, then we remove an edge e 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 v + f — h = v + (f — 1) — (h — 1) = 2.
The rest is finished by mathematical induction, c                                                                  D
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.
etr Hliněný,   Fl MU Brno                                              4                                Fl: MAOIO:  Planarity and drawings
Corollary 8.3. A simple planar graph on v > 3 vertices has < 3-y — 6 edges. A simple triangle-free planar graph on v > 3 vertices has < 2v — 4 edges, c
Proof: We can expect a connected graph G (since more edges can be added otherwise). Let G have h 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 h > ^ • 3/, implying %h > f.  From Theorem 8.2 we get
2                     1
2 = v -\- f — h <v -\- — h — h = v — — h
h < 3(v - 2) = 3« - 6.
For the other part, since G has now no triangles, every face is incident with at least 4 edges. Then h > ^ • 4/, and jh > f.  From Theorem 8.2 we get
2                     1
2 = v -\- f — h < v -\- — h — h = v — — h
h < 2(v - 2) = 2v - 4 .
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.
' Hlinený.   Fl Mt                                                                                                : MAOIO:  Planaritv and drawings
D
8.2    Recognizing and characterizing planar graphs
Quite interestingly, planarity can be efficiently tested, even in linear time. This results comes already from Tarjan, and it has been simplified several times since, but the algorithms are still not "easy".
Theorem 8.5. There is a linear-time algorithm deciding whether an input graph is planar.
Example 8.6.  We show that the graphs Ks and K3, 3 are not planar.
K
3,3
Ks has 5 vertices and 10 > 3 • 5 — 6 edges. ÍÍ33 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.             D
Corollary 8.7.   The graphs Ks and K3, 3 are not planar.
-*etr Hlinený,   hl MU Brr
Fl: MAOIO:  Planarity and drawings
24
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 beeen found by K. Kuratowski:
Theorem 8.8. A graph G is planar if and only if G contains no subdivision of Ks or K33, (as subgraphs).
etr Hliněný,   Fl MU Br
Fl: MAOIO:  Planarity and drawings
Example 8.9.       Which of the following graphs are planar? Find the planar embeddings, or prove nonplanarity of the graph(s).
Considering the two graphs for a while, we find out that A can be drawn as follows:
The graph B, on the other hand, is not planar by Theorem 8.8 since it contains a subdivision
of A3,3:
Detr Hlinený,   Fl MU Br
FhMAOlO:  Planarity and drawings
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 ^-connected planar graph G, a cycle C is facial if and only if G — V(C) is a connected subgraph.
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                                                 D
Corollary 8.11. Every two planar embeddings of a ^-connected graph are equivalent (i.e. having the same collection of facial cycles), c
Moreover (without proofs) we have:
Theorem 8.12.  Isomorphism testing of planar graphs can be done in linear time.
Theorem 8.13. Every simple planar graph has a planar embedding such that the edges are straight line segments.
8.3    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. c
The proof is, in both cases, very complicated, and relies on a computer search. 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, c
Moreover, the following generalized result has exceptionally beautiful proof:
Theorem 8.16.  Every loopless planar graph has the list chromatic number at most 5.c
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 of G 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.                                                                                                             D
______________leny,   Fl MU Brne                                                                                   :l: MAOIO:  Planarity and drawings
8.4    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.u
•   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.
etr Hliněný,   Fl MU Brno                                              11                               Fl: MAOIO:  Planarity and drawings