Greedy Convex Embeddings for Sensor Networks

Recent advances in systems of networked sensors have set the stage for smart environments which will have wide-ranging applications from intelligent wildlife monitoring to social applications such as health and elderly care service provisioning. Perhaps the most natural problem in sensor systems is the ¿efficient¿ propagation of a sensed local event. In order to address this problem, the notion of greedy embedding was defined by Papadimitriou and Ratajczak, where the authors conjectured that every 3-connected planar graph has a greedy embedding (possibly planar and convex) in the Euclidean plane. Recently, the greedy embedding conjecture was proved by Leighton and Moitra. However, their algorithm does not result in a drawing that is planar and convex in the Euclidean plane for all 3-connected planar graphs. Here we give a random algorithm for embedding 3-connected planar graphs a greedy convex embedding. Our convex embedding is especially useful for the case of sensor networks, where the position assigned to each sensor is the midpoint of the positions of its neighbors.