Compact Routing on Euclidian Metrics

Ittai Abraham Dahlia Malkhi
	Abstract We consider the problem of designing a compact communication network that supports efficient routing in a Euclidean plane. Our network design and routing scheme achieves $1+\epsilon$ stretch, logarithmic diameter, and constant out degree. This improves upon the best known result so far that requires a logarithmic out-degree. Furthermore, our scheme is asymptotically optimal in Euclidean metrics whose diameter is polynomial.
	[PODC version pdf]