SPECIAL
YEAR ON GRAPH THEORY AND COMBINATORIAL OPTIMIZATION
## Coxeter Lecture Series

Nov. 1-3, 1999

### "Geometric Representations of Graphs"

**László Lovász, ***Microsoft Research*

To represent a graph in a geometric way is a very natural and old problem.
For example, it was proved by Steinitz early in this century that every 3-connected
planar graph can be represented as the graph of vertices and edges of a (3-dimensional)
polytope.

Representability of a graph in various geometric fashions turns out to be
closely related to a number of basic properties and invariants of the graph:
chromatic number, clique number, connectivity, maximum cuts, etc. Moreover,
computing these representations often helps in the design of algorithms for
purely graph-theoretic problems.

Geometric Representations and Graph Properties

Orthogonal Representations and Semidefinite Optimization

Colin de Verdiere’s Invariant