- Lecturers: László Lovász and Katalin Vesztergombi
- Teaching Assistant: Gábor Lippner
- Time: Monday 2:30-4:00pm, Wednesday 3:00-4:30pm
- Location: Rényi Institute
- Text: Lecture Notes by L. Lovász. pdf
Currently updated: Chapters 1 through 8, new sections: 1.3, 2.2, 2.3. Sections with asterisk contain additional material not covered in this course.Background material on linear algebra, eigenvalues of graphs, polyhedra, and semidefinite optimization. A small fraction of this will be used (and quoted when used). Includes a bibliography.
- Homework #1 Note corrected deadline Sep 24! (Ask for extension if you need it because of the misprint in the date.)
- Homework #2 Deadline Oct 1
- Homework #3 Deadline Oct 15
- Homework #4 Deadline Oct 24
- Homework #5 Deadline Nov 12
- Homework #6 Deadline Nov 21
- Homework #7 Deadline Dec 10
Prerequisite: General mathematical experience on the undergraduate level with graph theory and linear algebra. 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.
Unit distance graphs. Bounds on the number of edges and on the chromatic number.
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.