  It has been shown by Indyk and Sidiropoulos [IS07] that any graph of genus
g>0 can be stochastically embedded into a distribution over planar graphs with
distortion 2^O(g). This bound was later improved to O(g^2) by Borradaile, Lee
and Sidiropoulos [BLS09]. We give an embedding with distortion O(log g), which
is asymptotically optimal. Apart from the improved distortion, another
advantage of our embedding is that it can be computed in polynomial time. In
contrast, the algorithm of [BLS09] requires solving an NP-hard problem. Our
result implies in particular a reduction for a large class of geometric
optimization problems from instances on genus-g graphs, to corresponding ones
on planar graphs, with a O(log g) loss factor in the approximation guarantee.
