On approximating planar metrics by tree metrics

✍ Scribed by Goran Konjevod; R. Ravi; F.Sibel Salman

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 92 KB
• Volume: 80
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(01)00161-2

✦ Synopsis

We combine the results of Bartal [Proc. 37th FOCS, 1996, pp. 184-193] on probabilistic approximation of metric spaces by tree metrics, with those of Klein, Plotkin and Rao [Proc. 25th STOC, 1993, pp. 682-690] on decompositions of graphs without small K s,s minors (such as planar graphs) to show that metrics induced by such graphs (with unit lengths on the edges) can be probabilistically approximated by tree metrics with an O(log diam G) distortion. This improves upon Bartal's result that holds for general n-node metrics with a distortion of O(log n log log n). The main ingredient of our proof is that weak probabilistic partitions suffice for the construction of tree metrics with low distortion, in contrast to strong partitions used by Bartal. We also show that our result is the best possible by providing a lower bound of (log diam G) for the distortion of any probabilistic approximation of the square grid by tree metrics.