Some Results on Greedy Embeddings in Metric Spaces
Some Results on Greedy Embeddings in Metric Spaces
复制标题
DOI：
10.1109/focs.2008.18
复制
发表时间：
2008-10
影响因子：
0.8
通讯作者：
Ankur Moitra;F. Leighton
中科院分区：
文献类型：
--
作者：
Ankur Moitra;F. Leighton
地理路由是路由算法的一个系列，它使用地理点位置作为路由目的的地址。这样的路由算法已被证明是既简单的实现和应用于无线传感器网络时，具有一定的效率。贪婪路由是这个模型的一个自然的抽象，在这个模型中，节点被分配在度量空间中的虚拟坐标，这些坐标被用来执行点对点路由。在这里，我们解决了Papadimitriou和Ratajczak的猜想，每个3连通平面图允许贪婪嵌入到欧几里得平面。这直接意味着所有排除K3，3作为子图的3连通图都允许贪婪嵌入到欧几里得平面中。我们还证明了一个组合的条件，保证nonembeddability。我们使用这个结果来构建图，可以greenly嵌入到欧几里得平面，但没有生成树承认这样的嵌入。
Geographic Routing is a family of routing algorithms that uses geographic point locations as addresses for the purposes of routing. Such routing algorithms have proven to be both simple to implement and heuristically effective when applied to wireless sensor networks. Greedy Routing is a natural abstraction of this model in which nodes are assigned virtual coordinates in a metric space, and these coordinates are used to perform point-to-point routing.Here we resolve a conjecture of Papadimitriou and Ratajczak that every 3-connected planar graph admits a greedy embedding into the Euclidean plane. This immediately implies that all 3-connected graphs that exclude K3,3 as a minor admit a greedy embedding into the Euclidean plane. We also prove a combinatorial condition that guarantees nonembeddability. We use this result to construct graphs that can be greedily embedded into the Euclidean plane, but for which no spanning tree admits such an embedding.