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).