Graphs and Geometry

Graphs are purely combinatorial objects. While it is natural for us to use geometry to visualize them in order to better grasp their structure, it is perhaps a bit surprising that representing a graph geometrically can significantly help to study its properties that have apparently nothing to do with geometry and also to devise algorithms for various graph problems. The purpose of the course is to present three topics where graphs and geometry couple in a nice way yielding arguably unexpected applications. The topics are chosen to display a broad spectrum of mathematical tools used in the development, study and use of various geometric representations of graphs while keeping the prerequisites reasonably low. The tools are ranging from elementary geometry, linear algebra and (elements of) differential geometry to probabilistic constructions, metric embeddings and optimization. The topics covered will be: 1) Coin representations of planar graphs—Koebe’s theorem, the Cage theorem. Applications: the planar separator theorem and a bound on the expansion of planar graphs. 2) Colin de Verdière’s graph parameter—its minor monotonicity, geometric characterizations it provides (outerplanarity, planarity, linkless embeddability), discussion of open problems Application: Steinitz’s representation of a planar graph. 3) Low distortion metric embeddings—distortion, the Johnson–Lindenstraus lemma, a random subset embedding, Bourgain’s theorem. Application: Algorithm to approximate the sparsest cut in a given graph.