The geometry of graphs and some of its algorithmic applications (Q1894703)

Techniques are explored for embedding a graph in a normed space of `small' dimension with `small distortion', i.e., distances between vertices in \(G\) are closely approximated by distances in the normed space of their images under the embedding. An efficient algorithm for such embeddings is introduced. Numerous applications are given, including multicommodity flow problems, decomposition into subgraphs of low diameter, and finding balanced separators.