# Greedy embedding

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Greedy_embedding
> Markdown URL: https://mediated.wiki/source/Greedy_embedding.md
> Source: https://en.wikipedia.org/wiki/Greedy_embedding
> Source revision: 1335683255
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [distributed computing](/source/distributed_computing) and [geometric graph theory](/source/geometric_graph_theory), '''greedy embedding''' is a process of assigning coordinates to the nodes of a [telecommunications network](/source/telecommunications_network) in order to allow [greedy](/source/greedy_algorithm) [geographic routing](/source/geographic_routing) to be used to route messages within the network. Although greedy embedding has been proposed for use in [wireless sensor network](/source/wireless_sensor_network)s, 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 [non-Euclidean geometry](/source/non-Euclidean_geometry). In this sense, greedy embedding may be viewed as a form of [graph drawing](/source/graph_drawing), in which an abstract graph (the communications network) is [embedded](/source/graph_embedding) into a geometric space.

The idea of performing geographic routing using coordinates in a virtual space, instead of using physical coordinates, is due to Rao et al.<ref name="rrpss03"/> Subsequent developments have shown that every network has a greedy embedding with succinct vertex coordinates in the [hyperbolic plane](/source/hyperbolic_plane), that certain graphs including the [polyhedral graph](/source/polyhedral_graph)s have greedy embeddings in the [Euclidean plane](/source/Euclidean_plane), and that [unit disk graph](/source/unit_disk_graph)s have greedy embeddings in Euclidean spaces of moderate dimensions with low stretch factors.

==Definitions==
In greedy routing, a message from a source node ''s'' to a destination node ''t'' travels to its destination by a sequence of steps through intermediate nodes, each of which passes the message on to a neighboring node that is closer to ''t''. If the message reaches an intermediate node ''x'' that does not have a neighbor closer to ''t'', then it cannot make progress and the greedy routing process fails. A greedy embedding is an embedding of the given graph with the property that a failure of this type is impossible. Thus, it can be characterized as an embedding of the graph with the property that for every two nodes ''x'' and ''t'', there exists a neighbor ''y'' of ''x'' such that ''d''(''x'',''t'')&nbsp;>&nbsp;''d''(''y'',''t''), where ''d'' denotes the distance in the embedded space.<ref name="pr05"/>

==Graphs with no greedy embedding==
[[File:Sextic-monomial-dessin.svg|thumb|150px|''K''<sub>1,6</sub>, a graph with no greedy embedding in the [Euclidean plane](/source/Euclidean_plane)]]
Not every graph has a greedy embedding into the [Euclidean plane](/source/Euclidean_plane); a simple counterexample is given by the [star](/source/Star_(graph_theory)) ''K''<sub>1,6</sub>, a [tree](/source/Tree_(graph_theory)) with one internal node and six leaves.<ref name="pr05"/> Whenever this graph is embedded into the plane, some two of its leaves must form an angle of 60 degrees or less, from which it follows that at least one of these two leaves does not have a neighbor that is closer to the other leaf.

In [Euclidean space](/source/Euclidean_space)s of higher dimensions, more graphs may have greedy embeddings; for instance, ''K''<sub>1,6</sub> has a greedy embedding into three-dimensional Euclidean space, in which the internal node of the star is at the origin and the leaves are a unit distance away along each coordinate axis. However, for every Euclidean space of fixed dimension, there are graphs that cannot be embedded greedily: whenever the number ''n'' is greater than the [kissing number](/source/kissing_number_problem) of the space, the graph ''K''<sub>1,''n''</sub> has no greedy embedding.<ref name="eg11"/>

==Hyperbolic and succinct embeddings==
Unlike the case for the Euclidean plane, every network has a greedy embedding into the [hyperbolic plane](/source/hyperbolic_plane). The original proof of this result, by [Robert Kleinberg](/source/Robert_Kleinberg), required the node positions to be specified with high precision,<ref name="k07"/> but subsequently it was shown that, by using a [heavy path decomposition](/source/heavy_path_decomposition) of a [spanning tree](/source/spanning_tree) of the network, it is possible to represent each node succinctly, using only a logarithmic number of bits per point.<ref name="eg11"/> In contrast, there exist graphs that have greedy embeddings in the Euclidean plane, but for which any such embedding requires a polynomial number of bits for the Cartesian coordinates of each point.<ref name="css09"/><ref name="adf10"/>

==Special classes of graphs==
===Trees===
The class of [trees](/source/Tree_(graph_theory)) that admit greedy embeddings into the Euclidean plane has been completely characterized, and a greedy embedding of a tree can be found in [linear time](/source/linear_time) when it exists.<ref name="np13"/>

For more general graphs, some greedy embedding algorithms such as the one by Kleinberg<ref name="k07"/> start by finding a [spanning tree](/source/spanning_tree) of the given graph, and then construct a greedy embedding of the spanning tree. The result is necessarily also a greedy embedding of the whole graph. However, there exist graphs that have a greedy embedding in the Euclidean plane but for which no spanning tree has a greedy embedding.<ref name="lm10"/>

===Planar graphs===
{{unsolved|mathematics|Does every [polyhedral graph](/source/polyhedral_graph) have a planar greedy embedding with convex faces?}}
{{harvtxt|Papadimitriou|Ratajczak|2005}} [conjecture](/source/conjecture)d that every [polyhedral graph](/source/polyhedral_graph) (a [3-vertex-connected](/source/k-vertex-connected_graph) [planar graph](/source/planar_graph), or equivalently by [Steinitz's theorem](/source/Steinitz's_theorem) the graph of a [convex polyhedron](/source/convex_polyhedron)) has a greedy embedding into the Euclidean plane.<ref name="pr05"/> By exploiting the properties of [cactus graph](/source/cactus_graph)s, {{harvtxt|Leighton|Moitra|2010}} proved the conjecture;<ref name="lm10"/><ref name="afg10"/> the greedy embeddings of these graphs can be defined succinctly, with logarithmically many bits per coordinate.<ref name="gs09"/>  However, the greedy embeddings constructed according to this proof are not necessarily planar embeddings, as they may include crossings between pairs of edges. For [maximal planar graph](/source/maximal_planar_graph)s, in which every face is a triangle, a greedy planar embedding can be found by applying the [Knaster–Kuratowski–Mazurkiewicz lemma](/source/Knaster%E2%80%93Kuratowski%E2%80%93Mazurkiewicz_lemma) to a weighted version of a [straight-line embedding](/source/F%C3%A1ry's_theorem) algorithm of Schnyder.<ref name="s90"/><ref name="d10"/> The '''strong Papadimitriou–Ratajczak conjecture''', that every [polyhedral graph](/source/polyhedral_graph) has a planar greedy embedding in which all faces are convex, remains unproven.<ref>{{citation
 | last1 = Nöllenburg | first1 = Martin
 | last2 = Prutkin | first2 = Roman
 | last3 = Rutter | first3 = Ignaz
 | doi = 10.20382/jocg.v7i1a3
 | issue = 1
 | journal = Journal of Computational Geometry
 | mr = 3463906
 | pages = 47–69
 | title = On self-approaching and increasing-chord drawings of 3-connected planar graphs
 | volume = 7
 | year = 2016| arxiv = 1409.0315| s2cid = 1500695
 }}.</ref>

===Unit disk graphs===
The wireless sensor networks that are the target of greedy embedding algorithms are frequently modeled as [unit disk graph](/source/unit_disk_graph)s, graphs in which each node is represented as a [unit disk](/source/unit_disk) and each edge corresponds to a pair of disks with nonempty intersection. For this special class of graphs, it is possible to find succinct greedy embeddings into a Euclidean space of polylogarithmic dimension, with the additional property that distances in the graph are accurately approximated by distances in the embedding, so that the paths followed by greedy routing are short.<ref name="fpw09"/>

==References==
{{reflist|30em|refs=
<ref name="adf10">{{citation
 | last1 = Angelini | first1 = Patrizio
 | last2 = Di Battista | first2 = Giuseppe
 | last3 = Frati | first3 = Fabrizio
 | contribution = Succinct greedy drawings do not always exist
 | doi = 10.1007/978-3-642-11805-0_17
 | pages = 171–182
 | series = Lecture Notes in Computer Science
 | title = Graph Drawing: 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers
 | volume = 5849
 | isbn = 978-3-642-11804-3
 | year = 2010| doi-access = free
 }}.</ref>
<ref name="afg10">{{citation
 | last1 = Angelini | first1 = Patrizio
 | last2 = Frati | first2 = Fabrizio
 | last3 = Grilli | first3 = Luca
 | doi = 10.7155/jgaa.00197
 | issue = 1
 | journal = [Journal of Graph Algorithms and Applications](/source/Journal_of_Graph_Algorithms_and_Applications)
 | mr = 2595019
 | pages = 19–51
 | title = An algorithm to construct greedy drawings of triangulations
 | volume = 14
 | year = 2010| doi-access = free
 }}.</ref>
<ref name="css09">{{citation
 | last1 = Cao | first1 = Lei
 | last2 = Strelzoff | first2 = A.
 | last3 = Sun | first3 = J. Z.
 | contribution = On succinctness of geometric greedy routing in Euclidean plane
 | doi = 10.1109/I-SPAN.2009.20
 | pages = 326–331
 | title = 10th International Symposium on Pervasive Systems, Algorithms, and Networks (ISPAN 2009)
 | year = 2009| isbn = 978-1-4244-5403-7
 | s2cid = 6513298
 }}.</ref>
<ref name="d10">{{citation
 | last = Dhandapani | first = Raghavan
 | doi = 10.1007/s00454-009-9235-6
 | issue = 2
 | journal = [Discrete and Computational Geometry](/source/Discrete_and_Computational_Geometry)
 | mr = 2579703
 | pages = 375–392
 | title = Greedy drawings of triangulations
 | volume = 43
 | year = 2010| s2cid = 11617189
 }}. See also</ref>
<ref name="eg11">{{citation
 | last1 = Eppstein | first1 = D. | author1-link = David Eppstein
 | last2 = Goodrich | first2 = M. T. | author2-link = Michael T. Goodrich
 | doi = 10.1109/TC.2010.257
 | issue = 11
 | journal = [IEEE Transactions on Computers](/source/IEEE_Transactions_on_Computers)
 | pages = 1571–1580
 | title = Succinct greedy geometric routing using hyperbolic geometry
 | volume = 60
 | year = 2011| bibcode = 2011ITCmp..60.1571E | s2cid = 40368995 }}.</ref>
<ref name="gs09">{{citation
 | last1 = Goodrich | first1 = Michael T. | author1-link = Michael T. Goodrich
 | last2 = Strash | first2 = Darren
 | contribution = Succinct greedy geometric routing in the Euclidean plane
 | doi = 10.1007/978-3-642-10631-6_79
 | location = Berlin
 | mr = 2792775
 | pages = 781–791
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Algorithms and Computation: 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009, Proceedings
 | volume = 5878
 | year = 2009| arxiv = 0812.3893| isbn = 978-3-642-10630-9 | s2cid = 15026956 }}.</ref>
<ref name="fpw09">{{citation
 | last1 = Flury | first1 = R.
 | last2 = Pemmaraju | first2 = S.V.
 | last3 = Wattenhofer | first3 = R.
 | title = IEEE Infocom 2009
 | contribution = Greedy routing with bounded stretch
 | doi = 10.1109/INFCOM.2009.5062093
 | pages = 1737–1745
 | isbn = 978-1-4244-3512-8
 | year = 2009| s2cid = 1881560
 }}.</ref>
<ref name="k07">{{citation
 | last = Kleinberg | first = R. | authorlink = Robert Kleinberg
 | contribution = Geographic routing using hyperbolic space
 | doi = 10.1109/INFCOM.2007.221
 | pages = 1902–1909
 | title = Proc. 26th IEEE International Conference on Computer Communications (INFOCOM 2007)
 | year = 2007| isbn = 978-1-4244-1047-7 | s2cid = 11845175 }}.</ref>
<ref name="lm10">{{citation
 | last1 = Leighton | first1 = Tom | authorlink = F. Thomson Leighton
 | last2 = Moitra | first2 = Ankur
 | doi = 10.1007/s00454-009-9227-6
 | issue = 3
 | journal = [Discrete and Computational Geometry](/source/Discrete_and_Computational_Geometry)
 | mr = 2679063
 | pages = 686–705
 | title = Some results on greedy embeddings in metric spaces
 | volume = 44
 | year = 2010| doi-access = free
 | hdl = 1721.1/80843
 | hdl-access = free
 }}.</ref>
<ref name="np13">{{citation
 | last1 = Nöllenburg | first1 = Martin
 | last2 = Prutkin | first2 = Roman
 | arxiv = 1306.5224
 | contribution = Euclidean greedy drawings of trees
 | title = Proc. 21st European Symposium on Algorithms (ESA 2013)
 | year = 2013| bibcode = 2013arXiv1306.5224N}}.</ref>
<ref name="pr05">{{citation
 | last1 = Papadimitriou | first1 = Christos H. | author1-link = Christos Papadimitriou
 | last2 = Ratajczak | first2 = David
 | doi = 10.1016/j.tcs.2005.06.022
 | issue = 1
 | journal = [Theoretical Computer Science](/source/Theoretical_Computer_Science_(journal))
 | mr = 2178923
 | pages = 3–14
 | title = On a conjecture related to geometric routing
 | volume = 344
 | year = 2005| doi-access = free
 }}.</ref>
<ref name="rrpss03">{{citation
 | last1 = Rao | first1 = Ananth
 | last2 = Ratnasamy | first2 = Sylvia
 | last3 = Papadimitriou | first3 = Christos H. | author3-link = Christos Papadimitriou
 | last4 = Shenker | first4 = Scott | author4-link = Scott Shenker
 | last5 = Stoica | first5 = Ion | author5-link = Ion Stoica
 | contribution = Geographic routing without location information
 | doi = 10.1145/938985.938996
 | pages = 96–108
 | title = Proc. 9th ACM Mobile Computing and Networking (MobiCom)
 | year = 2003| isbn = 1-58113-753-2
 | s2cid = 8374920
 }}.</ref>
<ref name="s90">{{Citation
  | last = Schnyder | first = Walter
  | chapter = Embedding planar graphs on the grid
  | url = http://portal.acm.org/citation.cfm?id=320176.320191
  | title = Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA)
  | year = 1990
  | pages = 138–148}}.</ref>
}}

Category:Geometric graph theory
Category:Routing algorithms
Category:Distributed computing
Category:Telecommunications

---
Adapted from the Wikipedia article [Greedy embedding](https://en.wikipedia.org/wiki/Greedy_embedding) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Greedy_embedding?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.