ICS Theory Group

November 14, Fall 2008: Theory Seminar

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.