Improved Stretch Factor for Bounded-Degree Planar Power Spanners of Wireless Ad-Hoc Networks

Given a wireless Ad-Hoc network modeled as a unit disk graph U in the plane, we present a localized distributed algorithm that constructs a bounded degree planar power spanner of U with a bounded stretch factor. More specifically, for an integer parameter k ≥ 8 and a power exponent constant p ε [2,5], our algorithm constructs a planar power spanner for the network of degree bounded by k+5 and a stretch factor bounded by 1 + 2^p sin^p(π/k). This significantly improves the previous best results in the literature by Song et al. and Wang et al..