Distributed Planarization and Local Routing Strategies in Sensor   Networks
  We present an algorithm which computes a planar 2-spanner from an Unit Disk Graph when the node density is sufficient. The communication complexity in terms of number of node's identifier sent by the algorithm is $6n$, while the computational complexity is $O(n\Delta)$, with $\Delta$ the maximum degree of the communication graph. Furthermore, we present a simple and efficient routing algorithm dedicated to the computed graph.   Last but not least, using traditional Euclidean coordinates, our algorithm needs the broadcast of as few as $3n$ node's identifiers. Under the hypothesis of sufficient node density, no broadcast at all is needed, reducing the previous best known complexity of an algorithm to compute a planar spanner of an Unit Disk Graph which was of $5n$ broadcasts. 
Aubin Jarry and Florian Huc and Pierre Leone and Jose Rolim
cs.NI