On succinct convex greedy drawing of 3-connected plane graphs
Xin He, Huaming Zhang · Symposium on Discrete Algorithms · 2011
Geometric routing by using virtual locations is an elegant way for solving network routing problems. In its simplest form, greedy routing, a message is simply for warded to a neighbor that is closer to the destination. It has been an open conjecture whether every 3-connected plane graph has a greedy drawing in R2 (by Papadimitriou and Ratajczak [23]). Leighton and Moitra [20] recently settled this conjecture positively. One main drawback of this approach is that the coordinates of the virtual locations requires Ω(n log n) bits to represent (the same space usage as traditional routing table approaches). This makes greedy routing infeasible in applications. A similar result was obtained by Angelini et al. [2]. However, neither of the two papers give the time efficiency analysis of their algorithms. In addition, as pointed out in [16], the drawings in these two papers are not necessarily planar nor convex.In this paper, we show that the classical Schnyder drawing in R2 of plane triangulations is greedy with respect to a simple natural metric function H(u, v) over R2 that is equivalent to Euclidean metric DE(u, v) (in the sense that DE(u, v)