A Localized Planarization Algorithm for Realistic Wireless Networks

Planar graph routing works provably correct if the underlying network graph is connected and planar. Typically, wireless networks modeled as 2D graphs, are not planar and planar graph routing applied on such unprocessed network graphs may fail. Planarizing a given connected graph by removing intersecting links might be impossible if the outcome still needs to be a connected subgraph. It becomes even more difficult with distributed planarization techniques, where each node is allowed to use only the information about its local neighborhood. Furthermore, it is getting complicated if the nodes' assigned positions do not reflect the exact physical location. With or without exact location information, the outcome might be disconnected, nonplanar, or both of it. With all these unsolvable problems, the question arises how to apply planar graph routing in a realistic network setting? Fortunately, wireless network graphs bear one property which distinguishes them from arbitrary graphs: due to limited communication range, network links cannot become arbitrarily long. In this work we exploit this locality property to build a new localized planarization algorithm, which is location fault tolerant and which produces planar connected graphs in most cases in realistic wireless models. We evaluate our algorithm using the Log Normal Shadowing model and show that our algorithm always produces planar connected graphs in all simulations even when large location errors are present.