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 sub-graph. 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, non-planar, or both of it.