Greedy embedding

<p>In <a href="/facts/Distributed_computing/o5nyhqTF">distributed computing</a> and <a href="/facts/Geometric_graph_theory/4vIAySX3">geometric graph theory</a>, greedy embedding is a process of assigning coordinates to the nodes of a <a href="/facts/Telecommunications_network/NFCX0STS">telecommunications network</a> in order to allow <a href="/facts/Greedy_algorithm/alfsekco">greedy</a> <a href="/facts/Geographic_routing/oGBKCwD3">geographic routing</a> to be used to route messages within the network. Although greedy embedding has been proposed for use in <a href="/facts/Wireless_sensor_network/r5LIAVsU">wireless sensor networks</a>, in which the nodes already have positions in physical space, these existing positions may differ from the positions given to them by greedy embedding, which may in some cases be points in a virtual space of a higher dimension, or in a <a href="/facts/Non-Euclidean_geometry/efKa7De2">non-Euclidean geometry</a>. In this sense, greedy embedding may be viewed as a form of <a href="/facts/Graph_drawing/uhh73BVo">graph drawing</a>, in which an abstract graph (the communications network) is <a href="/facts/Graph_embedding/IyBA3ttM">embedded</a> into a geometric space.
</p><p>The idea of performing geographic routing using coordinates in a virtual space, instead of using physical coordinates, is due to Rao et al. Subsequent developments have shown that every network has a greedy embedding with succinct vertex coordinates in the <a href="/facts/Hyperbolic_plane/DjTMKdgy">hyperbolic plane</a>, that certain graphs including the <a href="/facts/Polyhedral_graph/IKPCDH6r">polyhedral graphs</a> have greedy embeddings in the <a href="/facts/Euclidean_plane/tAUtRFcn">Euclidean plane</a>, and that <a href="/facts/Unit_disk_graph/oIhoT3Pr">unit disk graphs</a> have greedy embeddings in Euclidean spaces of moderate dimensions with low stretch factors.
</p>

Greedy embedding open-in-new

Greedy embedding