- Lecturer: László Lovász
- Time: Friday 12:15-13:45pm
- Location: 3.306
- Text: Lecture Notes by L. Lovász. pdf
Course description: The aim of the course is to describe various techniques for representing graphs in a geometrical way, and their use in proofs and in the design of algorithms. In the opposite direction, we describe examples of how graphs can be constructed from geometric objects to study their geometric properties. Topics:
Planar graphs, straight line drawing. Polyhedra and planarity, Steinitz's Theorem.
Rubber band representation, Tutte's method for drawing planar graphs. Applications of rubber band representations to non-planar graphs; connectivity testing. Rigidity of frameworks.
Touching circle representations. Koebe's and Andre'ev's theorems. Applications to planar separators and bisections.
The Colin de Verdiere number of a graph. Van der Holst's Lemma and characterizing planar graphs.
Orthogonal representations. Applications to Shannon capacity and perfect graphs.
Last modified September 19, 2009. This page is maintained by its owner.