Papadimitriou:2005:CRG:1121826.1121828
Summary
Papadimitriou, C. H. and Ratajczak, D. (2005) On a conjecture related to geometric routing. Theor. Comput. Sci., 344:3-14. ((URL))
Abstract
We conjecture that any planar 3-connected graph can be embedded in the plane in such a way that for any nodes s and t, there is a path from s to t such that the Euclidean distance to t decreases monotonically along the path. A consequence of this conjecture would be that in any ad hoc network containing such a graph as a spanning subgraph, two-dimensional virtual coordinates for the nodes can be found for which the method of purely greedy geographic routing is guaranteed to work. We discuss this conjecture and its equivalent forms show that its hypothesis is as weak as possible, and show a result delimiting the applicability of our approach: any 3-connected K3,3-free graph has a planar 3-connected spanning subgraph. We also present two alternative versions of greedy routing on virtual coordinates that provably work. Using Steinitz's theorem we show that any 3-connected planar graph can be embedded in three dimensions so that greedy routing works, albeit with a modified notion of distance; we present experimental evidence that this scheme can be implemented effectively in practice. We also present a simple but provably robust version of greedy routing that works for any graph with a 3-connected planar spanning subgraph.
Bibtex entry
@ARTICLE { Papadimitriou:2005:CRG:1121826.1121828,
AUTHOR = { Papadimitriou, C. H. and Ratajczak, D. },
TITLE = { On a conjecture related to geometric routing },
JOURNAL = { Theor. Comput. Sci. },
VOLUME = { 344 },
ISSUE = { 1 },
MONTH = { November },
YEAR = { 2005 },
ISSN = { 0304-3975 },
PAGES = { 3--14 },
NUMPAGES = { 12 },
URL = { http://dx.doi.org/10.1016/j.tcs.2005.06.022 },
ACMID = { 1121828 },
PUBLISHER = { Elsevier Science Publishers Ltd. },
ADDRESS = { Essex, UK },
KEYWORDS = { ad hoc networks, convex embeddings, geometric routing, greedy routing, planar embeddings, planar graphs },
ABSTRACT = { We conjecture that any planar 3-connected graph can be embedded in the plane in such a way that for any nodes s and t, there is a path from s to t such that the Euclidean distance to t decreases monotonically along the path. A consequence of this conjecture would be that in any ad hoc network containing such a graph as a spanning subgraph, two-dimensional virtual coordinates for the nodes can be found for which the method of purely greedy geographic routing is guaranteed to work. We discuss this conjecture and its equivalent forms show that its hypothesis is as weak as possible, and show a result delimiting the applicability of our approach: any 3-connected K3,3-free graph has a planar 3-connected spanning subgraph. We also present two alternative versions of greedy routing on virtual coordinates that provably work. Using Steinitz's theorem we show that any 3-connected planar graph can be embedded in three dimensions so that greedy routing works, albeit with a modified notion of distance; we present experimental evidence that this scheme can be implemented effectively in practice. We also present a simple but provably robust version of greedy routing that works for any graph with a 3-connected planar spanning subgraph. },
}