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
