A Lower Bound on Greedy Embedding in Euclidean Plane
Computing Sciences and Computer Engineering
Greedy embedding is the key of geometric greedy routing in p2p networks. It embeds a graph (the topological structure of the p2p network) in a metric space such that between any source-destination pair, there is a distance decreasing path for message delivery. It is known that any graph can be greedily embedded in the hyperbolic plane with using O(logn) bits for each node's coordinates . Interestingly, on greedy embedding in the Euclidean plane, existing embedding algorithms result in coordinates with Ω(��). It was recently proved that Ω(��) is a lower bound of the coordinates' bit length if one uses Cartesian or polar coordinate system and preserves the planar embedding of a planar graph when greedily embedding it in the Euclidean plan . In this paper we strengthen this result by further proving that Ω(��) is still a lower bound even if the graph is allowed to take free embedding in the plane.
Advances in Grid and Pervasive Computing
Sun, J. Z.
(2010). A Lower Bound on Greedy Embedding in Euclidean Plane. Advances in Grid and Pervasive Computing, 214-223.
Available at: https://aquila.usm.edu/fac_pubs/21520