Outline

• Drawings of graphs, planar graphs
  basic properties of planar drawings, faces, edge rotations, and duality
• Planar drawings and Euler's formula
  polygonal drawings, Jordan curve theorem vs. Euler's formula, bounding the number of edges of a planar graph
• Characterization of planar graphs
  non-planarity of K5 and K3,3, the Kuratowski theorem, uniqueness of drawing
• Appendix: Colouring maps and planar graphs

Goals

The purpose of this lecture is to give a thorough introduction to planar graphs (those without "crossings" of edges), their basic properties, Euler's formula, and Kuratowski's characterization of planarity. From historical perspectives, planar graphs are tied with geometric polyhedra (18th cent.) and with the famous Four Colour Problem (19th cent.) mentioned already in Lecture 6. Practical importance of planar graphs is quite obvious -- in many applications, planarity and no-crossings is essential or unavoidable.

Course book [Invitation to Discrete Mathematics (by Jiří Matoušek, Jaroslav Nešetřil)]:

Study Sections 6.1, 6.2, and 6.3. However, most of the content of 6.1 (about other surfaces) can be left till future Lecture 11. (In the Czech edition, the Sections are 6.1-6.7.)

Advanced course book [Graph theory (by Reinhard Diestel)]:

Study Sections 4.2 and 4.4, and starting parts of 4.1 and 4.3 and voluntarily 4.6.

 

We suggest mainly the first book [Matoušek-Nešetřil] (and its Czech edition) for accessible initial study of planar graphs.