On the Planarization of Wireless Sensor Networks Academic Article

abstract

• 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. Springer Science+Business Media, LLC 2009.

authors

• Chen, Jianer
• Jiang, Anxiao (Andrew)

published proceedings

• ALGORITHMICA

author list (cited authors)

• Zhang, F., Jiang, A. A., & Chen, J.

citation count

• 2

complete list of authors

• Zhang, Fenghui||Jiang, Anxiao Andrew||Chen, Jianer

publication date

• July 2011

publisher

• Springer Nature  Publisher

published in

• Algorithmica: an international journal in computer science  Journal

keywords

• Approximation Algorithm
• Bipartite Planarization
• Graph Drawing
• Network Planarization
• Parameterized Algorithm
• Sensor Network

Digital Object Identifier (DOI)

• 10.1007/s00453-010-9476-z

start page

• 593

end page

• 608

volume

• 60

issue

• 3

URL

• http%3A%2F%2Fdx.doi.org%2F10.1007%2Fs00453-010-9476-z