Succinct Strictly Convex Greedy Drawing of 3-Connected Plane Graphs

Geometric routing by using virtual locations is an elegant way for solving network routing problems. Greedy routing, where a message is simply forwarded to a neighbor that is closer to the destination, is a simple form of geometric routing. Papadimitriou and Ratajczak conjectured that every 3-connected plane graph has a greedy drawing in the

$\mathcal R^2$

plane [10]. Leighton and Moitra settled this conjecture positively in [9]. However, their drawings have two major drawbacks: (1) their drawings are not necessarily planar; and (2) Ω(

n

log

n

) bits are needed to represent the coordinates of their drawings, which is too large for routing algorithms for wireless networks. Recently, He and Zhang [8] showed that every triangulated plane graph has a succinct (using

O

(log

n

) bit coordinates) greedy drawing in

$\mathcal R^2$

plane with respect to a metric function derived from Schnyder realizer. However, their method fails for 3-connected plane graphs. In this paper, we show that every 3-connected plane graph has drawing in the

$\mathcal R^2$

plane, that is succinct, planar, strictly convex, and is greedy with respect to a metric function based on parameters derived from Schnyder wood.