SODA Conference 2011 Conference Paper
On Succinct Convex Greedy Drawing of 3-Connected Plane Graphs
- Xin He 0005
- Huaming Zhang
Geometric routing by using virtual locations is an ele gant 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 R 2 (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 repre sent (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 2 of plane triangulations is greedy with respect to a simple natural metric function H ( u, v ) over R 2 that is equivalent to Euclidean metric D E ( u, v ) (in the sense that D E ( u, v ) < H ( u, v ) ≤ 2√2 D E ( u, v ).) The drawing is succinct, using two integer coordinates between 0 and 2 n − 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 2 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 ).