The Geometry of Graphs

Nati Linial

In this talk we explore some implications of viewing graphs as geometric objects. This approach offers a new perspective on a number of graph-theoretic and algorithmic problems. I will mention several ways to model graphs geometrically, but our main concern will be with geometric representations that respect the metric of the (possibly weighted) graph. Given a graph we map its vertices to a normed space in an attempt to (i) Keep down the dimension of the host space and (ii) Guarantee a small distortion, i.e., make sure that distances between vertices closely match the distances between their geometric images. I will present the best known (existential and algorithmic) results on this problem and then mention some interesting properties that graphs with good embeddings have.

Much of this work was done jointly with Yuri Rabinovich (Cornell) and Eran London (Jerusalem).