Authors: Xin He Huaming Zhang
Publish Date: 2012/08/25
Volume: 68, Issue: 2, Pages: 531-544
Abstract
Geometric routing by using virtual locations is an elegant way for solving network routing problems In its simplest form greedy routing a message is simply forwarded to a neighbor that is closer to the destination It has been an open conjecture whether every 3connected plane graph has a greedy drawing in the Euclidean plane R 2 by Papadimitriou and Ratajczak in Theor Comp Sci 34413–14 2005 Leighton and Moitra Discrete Comput Geom 443686–705 2010 recently settled this conjecture positively One main drawback of this approach is that the coordinates of the virtual locations require Ωnlogn bits to represent the same space usage as traditional routing table approaches This makes greedy routing infeasible in applicationsIn this paper we show that the classical Schnyder drawing in R 2 of plane triangulations is greedy with respect to a simple natural metric function Huv over R 2 that is equivalent to Euclidean metric D E uv in the sense that D Euv leq Huv leq2sqrt2D Euv The drawing uses two integer coordinates between 0 and 2n−5 which can be represented by logn bits We also show that the classical Schnyder drawing in R 2 of 3connected plane graphs is weakly greedy with respect to the same metric function H∗∗ The drawing uses two integer coordinates between 0 and f where f is the number of internal faces of G
Keywords: