A Lower Bound on Greedy Embedding in Euclidean Plane
Document Type
Book Chapter
Publication Date
4-23-2010
School
Computing Sciences and Computer Engineering
Abstract
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
214
Last Page
223
Recommended Citation
Cao, L.,
Strelzoff, A.,
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
COinS