A Lower Bound on Greedy Embedding in Euclidean Plane

Document Type

Book Chapter

Publication Date



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 [7]. 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 [2]. 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.

Publication Title

Advances in Grid and Pervasive Computing

First Page


Last Page