On succinct convex greedy drawing of 3-connected plane graphs

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 forwarded 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 R² (by Papadim-itriou 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 R² of plane triangulations is greedy with respect to a simple natural metric function H(u, v) over R² that is equivalent to Euclidean metric D _E(u, v) (in the sense that DE{u,v) ≤ H(u,v) ≤ 2√2D _E(u,v).) The drawing is succinct, using two integer coordinates between 0 and 2n - 5. For 3-connected plane graphs, there is another conjecture by Papadimitriou and Ratajczak (as stated in [16]): Convex Greedy Embedding Conjecture: Every 3-connected planar graph has a convex greedy embedding in the Euclidean plane. In a recent paper [6], Cao et al. provided a plane graph G and showed that any convex greedy embedding of G in Euclidean plane must use Ω (n)-bit coordinates. Thus, if we add the succinctness requirement, the Convex Greedy Embedding Conjecture is false. In this paper, we show that the classical Schnyder drawing in R² of 3-connected plane graphs is weakly greedy with respect to the same metric function H(*, *). The drawing is planar, convex, and succinct, using two integer coordinates between 0 and f (where f is the number of internal faces of G).