On approximating planar metrics by tree metrics

We combine the results of Bartal [Proc. 37th FOCS, 1996, pp. 184-193] on pr obabilistic approximation of metric spaces by tree metrics, with those of K lein, Plotkin and Rao [Proc. 25th STOC, 1993, pp. 682-690] on decomposition s of graphs without small K-s,K-s minors (such as planar graphs) to show th at metrics induced by such graphs (with unit lengths on the edges) can be p robabilistically approximated by tree metrics with an O(log diam G) distort ion. This improves upon Bartal's result that holds for general n-node metri cs with a distortion of O(log n log log n). The main ingredient of our proo f is that weak probabilistic partitions suffice for the construction of tre e metrics with low distortion, in contrast to strong partitions used by Bar tal. We also show that our result is the best possible by providing a lower bound of Omega (log diam G) for the distortion of any probabilistic approx imation of the square grid by tree metrics. (C) 2001 Elsevier Science B.V. All rights reserved.