We shall discuss the present state of the following intriguing question:
Is it true that the shortest-path metric of any planar graph can be embedded into L_1 with a constant distortion?
Or, equivalently (though the equivalence is not obvious),
Is it true that for multicommodity flows on planar networks, the gap between the MinCut and the MaxFlow is at most constant?The older related findings include, e.g., the Okamura-Seymour's Theorem implying that any disc metric is isometrically embeddable into L_1, and Seymour's Theorem implying that the restriction of the shortest path metric of a weighted planar graph G to its set of edges E(G) can be extended to an L_1 embeddable metric on V(G). Another related result, due to Klein-Plotkin-Rao claims, in the language of metrics, that for a planar graph G it always holds: EdgeExpansion(G) x AverageDistance(G) = O(1).
The more recent results include Rao's proof that a metric of a weighted planar graph can be embedded into L_2 (and hence L_1) with distortion at most O(log n)^0.5, and [GNSR] proof of the conjecture for K_4-free graphs.