101. A Lower Bound on Greedy Embedding in Euclidean Plane
- Author
-
Andrew Strelzoff, Lei Cao, and Jonathan Z. Sun
- Subjects
Planar straight-line graph ,Linkless embedding ,Graph embedding ,law.invention ,Planar graph ,Combinatorics ,symbols.namesake ,Greedy embedding ,law ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,symbols ,Graph (abstract data type) ,Embedding ,Cartesian coordinate system ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - 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 \Omega}(n)$ bits It was recently proved that ${\it \Omega}(n)$ 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 ${\it \Omega}(n)$ is still a lower bound even if the graph is allowed to take free embedding in the plane.
- Published
- 2010