### Algorithms and Complexity Seminar

## A Solution to the Papadimitriou-Ratajczak conjecture

### Ankur Moitra (MIT)

{\em Geographic Routing} is a family of routing algorithms that uses
geographic point locations as addresses for the purposes of routing. Such
routing algorithms have proven to be both simple to implement and heuristically
effective when applied to wireless sensor networks. {\em Greedy Routing} is a
natural abstraction of this model in which nodes are assigned virtual
coordinates in a metric space, and these coordinates are used to perform
point-to-point routing.

Here we resolve a conjecture of Papadimitriou and Ratajczak that every
$3$-connected planar graph admits a greedy embedding into the Euclidean plane.
This immediately implies that all $3$-connected graphs that exclude $K_{3,3}$
as a minor admit a greedy embedding into the Euclidean plane. Additionally, we
provide the first non-trivial examples of graphs that admit no such embedding.
These structural results provide efficiently verifiable certificates that a
graph admits a greedy embedding or that a graph admits no greedy embedding into
the Euclidean plane.