distributed computing A distributed system is a system whose components are located on different networked computers, which communicate and coordinate their actions by passing messages to one another from any system. Distributed computing is a field of computer sci ...

and

geometric graph theory Geometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geome ...

, greedy embedding is a process of assigning coordinates to the nodes of a

telecommunications network A telecommunications network is a group of nodes interconnected by telecommunications links that are used to exchange messages between the nodes. The links may use a variety of technologies based on the methodologies of circuit switching, mes ...

in order to allow greedy

geographic routing Geographic routing (also called georouting or position-based routing) is a routing principle that relies on geographic position information. It is mainly proposed for wireless networks and based on the idea that the source sends a message to the g ...

to be used to route messages within the network. Although greedy embedding has been proposed for use in wireless sensor networks, 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 In mathematics, non-Euclidean geometry consists of two geometries based on axioms closely related to those that specify Euclidean geometry. As Euclidean geometry lies at the intersection of metric geometry and affine geometry, non-Euclidean g ...

. In this sense, greedy embedding may be viewed as a form of

graph drawing Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, c ...

, in which an abstract graph (the communications network) is embedded 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. Subsequent developments have shown that every network has a greedy embedding with succinct vertex coordinates in the

hyperbolic plane In mathematics, hyperbolic geometry (also called Lobachevskian geometry or Bolyai– Lobachevskian geometry) is a non-Euclidean geometry. The parallel postulate of Euclidean geometry is replaced with: :For any given line ''R'' and point ' ...

, that certain graphs including the

polyhedral graph In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-con ...

s have greedy embeddings in the

Euclidean plane In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions ...

, and that

unit disk graph In geometric graph theory, a unit disk graph is the intersection graph of a family of unit disks in the Euclidean plane. That is, it is a graph with one vertex for each disk in the family, and with an edge between two vertices whenever the corre ...

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'') > ''d''(''y'',''t''), where ''d'' denotes the distance in the embedded space.

Graphs with no greedy embedding

Not every graph has a greedy embedding into the

; a simple counterexample is given by the

star A star is an astronomical object comprising a luminous spheroid of plasma (physics), plasma held together by its gravity. The List of nearest stars and brown dwarfs, nearest star to Earth is the Sun. Many other stars are visible to the naked ...

''K''_1,6, a

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...

with one internal node and six leaves. 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 Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidea ...

s of higher dimensions, more graphs may have greedy embeddings; for instance, ''K''_1,6 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 In geometry, the kissing number of a mathematical space is defined as the greatest number of non-overlapping unit spheres that can be arranged in that space such that they each touch a common unit sphere. For a given sphere packing (arrangement o ...

of the space, the graph ''K''_1,''n'' has no greedy embedding.

Hyperbolic and succinct embeddings

Unlike the case for the Euclidean plane, every network has a greedy embedding into the

. The original proof of this result, by Robert Kleinberg, required the node positions to be specified with high precision, but subsequently it was shown that, by using a heavy path decomposition of a

spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is ...

of the network, it is possible to represent each node succinctly, using only a logarithmic number of bits per point. 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.

Special classes of graphs

Trees

The class of

trees In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are u ...

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 In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

when it exists. For more general graphs, some greedy embedding algorithms such as the one by Kleinberg start by finding a

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.

Planar graphs

conjecture In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in ...

d that every

(a 3-vertex-connected

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...

, or equivalently by

Steinitz's theorem In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar gra ...

the graph of a

convex polyhedron A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...

) has a greedy embedding into the Euclidean plane. By exploiting the properties of

cactus graph In graph theory, a cactus (sometimes called a cactus tree) is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or ...

s, proved the conjecture; the greedy embeddings of these graphs can be defined succinctly, with logarithmically many bits per coordinate. 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 graphs, in which every face is a triangle, a greedy planar embedding can be found by applying the

Knaster–Kuratowski–Mazurkiewicz lemma The Knaster–Kuratowski–Mazurkiewicz lemma is a basic result in mathematical fixed-point theory published in 1929 by Knaster, Kuratowski and Mazurkiewicz. The KKM lemma can be proved from Sperner's lemma and can be used to prove the Brouwer ...

to a weighted version of a straight-line embedding algorithm of Schnyder. The strong Papadimitriou–Ratajczak conjecture, that every

has a planar greedy embedding in which all faces are convex, remains unproven..

Unit disk graphs

The wireless sensor networks that are the target of greedy embedding algorithms are frequently modeled as

s, graphs in which each node is represented as a

unit disk In mathematics, the open unit disk (or disc) around ''P'' (where ''P'' is a given point in the plane), is the set of points whose distance from ''P'' is less than 1: :D_1(P) = \.\, The closed unit disk around ''P'' is the set of points whose d ...

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.

References

{{reflist, 30em, refs= {{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 , year = 2010, doi-access = free . {{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 The ''Journal of Graph Algorithms and Applications'' is an open access peer-reviewed scientific journal covering the subject of graph algorithms and graph drawing. The journal was established in 1997 and the editor-in-chief is Giuseppe Liotta (Univ ...

, mr = 2595019 , pages = 19–51 , title = An algorithm to construct greedy drawings of triangulations , volume = 14 , year = 2010, doi-access = free . {{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. {{citation , last = Dhandapani , first = Raghavan , doi = 10.1007/s00454-009-9235-6 , issue = 2 , journal = Discrete and Computational Geometry , mr = 2579703 , pages = 375–392 , title = Greedy drawings of triangulations , volume = 43 , year = 2010. See also {{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 ''IEEE Transactions on Computers'' is a monthly peer-reviewed scientific journal covering all aspects of computer design. It was established in 1952 and is published by the IEEE Computer Society. The editor-in-chief is Ahmed Louri, David and Mari ...

, pages = 1571–1580 , title = Succinct greedy geometric routing using hyperbolic geometry , volume = 60 , year = 2011. {{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. {{citation , last1 = Flury , first1 = R. , last2 = Pemmaraju , first2 = S.V. , last3 = Wattenhofer , first3 = R. , contribution = Greedy routing with bounded stretch , doi = 10.1109/INFCOM.2009.5062093 , pages = 1737–1745 , title = IEEE INFOCOM 2009 , year = 2009. {{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. {{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 , mr = 2679063 , pages = 686–705 , title = Some results on greedy embeddings in metric spaces , volume = 44 , year = 2010, doi-access = free . {{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. {{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 computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumscribe the ...

, mr = 2178923 , pages = 3–14 , title = On a conjecture related to geometric routing , volume = 344 , year = 2005, doi-access = free . {{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. {{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. Geometric graph theory Routing algorithms Distributed computing Telecommunications