### Abstract

A graph drawing is *greedy* if, for every ordered pair of vertices $(x,y)$, there is a path from $x$ to $y$ such that the Euclidean distance to $y$ decreases monotonically at every vertex of the path. Greedy drawings support a simple geometric routing scheme, in which any node that has to send a packet to a destination ``greedily’’ forwards the packet to any neighbor that is closer to the destination than itself, according to the Euclidean distance in the drawing. In a greedy drawing such a neighbor always exists and hence this routing scheme is guaranteed to succeed.

In 2004 Papadimitriou and Ratajczak stated two conjectures related to greedy drawings. The *greedy embedding conjecture** states that every $3$-connected planar graph admits a greedy drawing. The **convex greedy embedding conjecture** asserts that every $3$-connected planar graph admits a planar greedy drawing in which the faces are delimited by convex polygons. In 2008 the greedy embedding conjecture was settled in the positive by Leighton and Moitra. *

In this paper we prove that every $3$-connected planar graph admits a *planar** greedy drawing. Apart from being a strengthening of Leighton and Moitra’s result, this theorem constitutes a natural intermediate step towards a proof of the convex greedy embedding conjecture.*

*
*
Publication

Discrete & Computational Geometry

###### Assistant Professor (RTDb)

My research interests are in Algorithm Engineering and Complexity, focused in particular on the theoretical and algorithmic challenges arising from the visualization of graphs.