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+ϵ)‐approximation algorithm and an FPT algorithm for the bipartite planarization problem.