On the Planarization of Wireless Sensor Networks

Network planarization has been an important technique in numerous sensornet protocols-such as Greedy Perimeter Stateless Routing (GPSR), topology discovery, data-centric storage, etc.-however the planarization process itself has been difficult. Known efficient planarization algorithms exist only for restrictive wireless network models: unit-disk graphs with accurately known location information. In this paper, we study efficient planarization of wireless sensor networks, and present a novel planarization method for a more general network model, where sensors can have non-uniform transmission ranges and no location information is needed. Our planarization algorithms also include a (2+epsilon)-approximation algorithm and an FPT algorithm for the bipartite planarization problem.