Algorithm for greedy routing based on the Thurston algorithm in sensor networks

Abstract

In this paper we present a greedy routing scheme for planar 3-connected graphs. The embedding is in R <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> , but the proximity measure used is not Euclidean. We show the relationship between our embedding and classical circle packings and described a modification of the Thurston algorithm originally designed for generating circle packings, so that it is able to generate the embeddings required to support greedy power routing on a sensor network.