In wireless networks, greedy routing is a method of routing message from source to destination in which the current vertex, holding the message, sends the message to its neighbor whose geographic distance from destination is minimum among all its neighbors. This method often suffers a problem of local minima. A local minimum is a situation in which the vertex which is holding the message is closer to the destination than any of its neighbors and destination is not its neighbor. Various methods have been proposed for getting out of local minima but they have different limitations imposed on them.
Recently, more robust solutions for getting out of local minima have been proposed based on the idea of assigning to each vertex a virtual coordinate in some metric space. One of the methods is greedy routing using an embedding of the graph topology into the hyperbolic plane. This method uses a spanning tree of the graph, embedded into the hyperbolic plane, and guarantees that the message will always reach the destination. However, it also has a limitation that the message may take a very long route even if a shorter route exists in the graph.
In our work, we propose a method of greedy routing in a graph with the aid of its spanning tree and we investigate the problem of selecting a "good" spanning tree in a graph such that the greedy routing using this tree guaranties relatively short greedy routing paths. The experiments are performed on different types of graphs, like Random graphs, Unit Disk graphs and Power Law graphs, and different densities (dense, average dense and sparse). The spanning trees used for greedy routing are Breadth First Search, Depth First Search, Minimum Spanning Tree (Prim's algorithm), Dijkstra's algorithm (weighted variant of breadth first search) and Hamiltonian path (weighted variant of Depth First Search). The experiments results compare greedy paths generated by these spanning trees in terms of stretch factor, and give preferences for selecting a spanning tree for greedy routing for a given graph type and graph's density type.