caa a22 4500 445804335 CHVBK 20180317145152.0 cr unu---uuuuu 170323e20110701xx s 000 0 eng 10.1007/s00453-010-9476-z doi (NATIONALLICENCE)springer-10.1007/s00453-010-9476-z On the Planarization of Wireless Sensor Networks [Elektronische Daten] [Fenghui Zhang, Anxiao Jiang, Jianer Chen] 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, 2010 Sensor network nationallicence Network planarization nationallicence Graph drawing nationallicence Bipartite planarization nationallicence Approximation algorithm nationallicence Parameterized algorithm nationallicence Zhang Fenghui Department of Computer Science & Engineering, Texas A&M University, 77843, College Station, TX, USA aut Jiang Anxiao Department of Computer Science & Engineering, Texas A&M University, 77843, College Station, TX, USA aut Chen Jianer Department of Computer Science & Engineering, Texas A&M University, 77843, College Station, TX, USA aut Algorithmica Springer-Verlag 60/3(2011-07-01), 593-608 0178-4617 60:3<593 2011 60 453 https://doi.org/10.1007/s00453-010-9476-z text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9476-z text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Zhang Fenghui Department of Computer Science & Engineering, Texas A&M University, 77843, College Station, TX, USA aut NATIONALLICENCE 700 1- Jiang Anxiao Department of Computer Science & Engineering, Texas A&M University, 77843, College Station, TX, USA aut NATIONALLICENCE 700 1- Chen Jianer Department of Computer Science & Engineering, Texas A&M University, 77843, College Station, TX, USA aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/3(2011-07-01), 593-608 0178-4617 60:3<593 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer