Some Results on Greedy Embeddings in Metric Spaces (FOCS 2008)
By Tom Leighton and Ankur Moitra
Presented by Darren Strash
I will discuss a recent proof that resolves a conjecture of Papadimitriou and
Ratajczak---that every 3-connected planar graph admits a
greedy embedding into the Euclidean plane.