Greedy embedding

The idea of performing geographic routing using coordinates in a virtual space, instead of using physical coordinates, is due to Rao et al.[1] Subsequent developments have shown that every network has a greedy embedding with succinct vertex coordinates in the hyperbolic plane, that certain graphs including the polyhedral graphs have greedy embeddings in the Euclidean plane, and that unit disk graphs have greedy embeddings in Euclidean spaces of moderate dimensions with low stretch factors.

[2] Not every graph has a greedy embedding into the Euclidean plane; a simple counterexample is given by the star K1,6, a tree with one internal node and six leaves.

The original proof of this result, by Robert Kleinberg, required the node positions to be specified with high precision,[4] but subsequently it was shown that, by using a heavy path decomposition of a spanning tree of the network, it is possible to represent each node succinctly, using only a logarithmic number of bits per point.

[11][12] The strong Papadimitriou–Ratajczak conjecture, that every polyhedral graph has a planar greedy embedding in which all faces are convex, remains unproven.

For this special class of graphs, it is possible to find succinct greedy embeddings into a Euclidean space of polylogarithmic dimension, with the additional property that distances in the graph are accurately approximated by distances in the embedding, so that the paths followed by greedy routing are short.