Lectures on Planar Graphs

Sommersemester 2008
Prof. Stefan Felsner

LV-Nr.: 0230 L 253
Mo 10-12, MA 542
Di 10-12, MA 542

Contents:

Planar graphs are very appealing objects. Drawings and visualizations make it pleasent to work with them, still they connect to other importent mathematical fields, e.g., topology or statistical physics. I hope to prove to my audience that there is a lot of beautiful mathematics in planar graphs. A selection of topics for the course:
  1. Jordan curve theorem and dual graphs
  2. Euler's formula
  3. Characterizations
  4. Hanani-Tutte theorem
  5. Planarity testing algorithms
  6. Drawings of planar graphs
  7. Steinitz theorem
  8. Counting planar structures
  9. Floor plans and squarings
  10. Coloring planar graphs
  11. Hamiltonicity: Tutte's theorem and Barnette's conjecture
  12. Pfaffian orientations and the Tutte polynomial
  13. Lattices of orientations
  14. Art gallery problems
  15. Delaunay triangulations
  16. Crossing numbers and geometric graphs
  17. Pseudotriangulations
  18. Planar posets

Prerequisites and Context:

Some basic knowledge in linear algebra and graph theory will be helpful.

The cours is part of the "Discrete Structures" course series, see Diskrete Strukturen

Exercises:

Di 14-16
MA 542

In the first exercise session we will settle the format of the exercises.
As a wrmup yo may try the following:
  1. Find a planar embedding (i.e., an embedding without crossing edges) of the following graph:


  2. Find all possible ways of placing four points in the plane such that their pairwise distances take only two values.

Literature:

Large parts of the course will be based on original journal articles. The following is a list of books containing relevant material:
Zuletzt bearbeitet 8. April 2008