- 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. Approximation of maximum cut.
Touching circle representations. Koebe's and Andre'ev's theorems. Applications to planar bisections.
Square tiling representations. The theorems of Brooks-Smith-Stone-Tutte and Schramm.
Orthogonal representations. The theta-function and its application to Shannon capacity and to coloring algorithms with small number of colors. The minimum dimension, connection with connectivity.
Last modified December 4, 2009. This page is
maintained by its owner.