{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:47:38Z","timestamp":1787323658316,"version":"build-2736575974"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2006,1]]},"abstract":"<jats:p>We show that the shortest-path metric of any k-outerplanar graph, for any fixed k, can be approximated by a probability distribution over tree metrics with constant distortion and hence also embedded into $\\ell_1$ with constant distortion. These graphs play a central role in polynomial time approximation schemes for many NP-hard optimization problems on general planar graphs and include the family of weighted $k\\times n$ planar grids. This result implies a constant upper bound on the ratio between the sparsest cut and the maximum concurrent flow in multicommodity networks for k-outerplanar graphs, thus extending a theorem of Okamura and Seymour [J. Combin. Theory Ser. B, 31 (1981), pp. 75-81] for outerplanar graphs, and a result of Gupta et al. [Combinatorica, 24(2004), pp. 233-269] for treewidth-2 graphs. In addition, we obtain improved approximation ratios for k-outerplanar graphs on various problems for which approximation algorithms are based on probabilistic tree embeddings. We conjecture that these embeddings for k-outerplanar graphs may serve as building blocks for $\\ell_1$ embeddings of more general metrics.<\/jats:p>","DOI":"10.1137\/s0895480102417379","type":"journal-article","created":{"date-parts":[[2006,3,27]],"date-time":"2006-03-27T21:00:21Z","timestamp":1143493221000},"page":"119-136","source":"Crossref","is-referenced-by-count":36,"title":["Embedding k-Outerplanar Graphs into l1"],"prefix":"10.1137","volume":"20","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anupam","family":"Gupta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ilan","family":"Newman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuri","family":"Rabinovich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alistair","family":"Sinclair","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,1]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792224474"},{"key":"R2","unstructured":"A.Andoni, M.Deza, A.Gupta, P.Indyk, S.Raskhodnikova, Lower bounds for embedding edit distance into normed spaces, ACM, New York, 2003, 523\u2013526MR1974961"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"SanjeevArora, SatishRao, UmeshVazirani, Expander flows, geometric embeddings and graph partitioning, ACM, New York, 2004, 222\u20132312005j:68081","DOI":"10.1145\/1007352.1007355"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794285983"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"B. Awerbuch and Y. Azar,\n                      Buy\u2010at\u2010bulk network design\n                      , in Proceedings of the 38th Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Los Alamitos, CA, 1997, pp. 542\u2013547.","DOI":"10.1109\/SFCS.1997.646143"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174650"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"YairBartal, Probabilistic approximation of metric spaces and its algorithmic applications, IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, 184\u2013193MR1450616","DOI":"10.1109\/SFCS.1996.548477"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"Y. Bartal,\n                      On approximating arbitrary metrics by tree metrics\n                      , in Proceedings of the 30th ACM Symposium on Theory of Computing (STOC), ACM, New York, 1998, pp. 161\u2013168.","DOI":"10.1145\/276698.276725"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840379"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02776078"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"M. Charikar, C. Chekuri, A. Goel, S. Guha, and S. A. Plotkin,\n                      Approximating a finite metric by a small number of tree metrics\n                      , in Proceedings of the 39th Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Los Alamitos, CA, 1998, pp. 379\u2013388.","DOI":"10.1109\/SFCS.1998.743488"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04295-9"},{"key":"R14","volume-title":"Graph theory","author":"Diestel Reinhard","year":"2000"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"R16","unstructured":"Andr\u00e1sFrank, Packing paths, circuits, and cuts\u2014a survey, Algorithms Combin., Vol. 9, Springer, Berlin, 1990, 47\u201310091i:68116"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1096"},{"key":"R18","unstructured":"AnupamGupta, Steiner points in tree metrics don\u2019t (really) help, SIAM, Philadelphia, PA, 2001, 220\u2013227MR1958411"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0015-x"},{"key":"R20","unstructured":"R.Halin, Studies on minimallyn\u2010connected graphs, Academic Press, London, 1971, 129\u201313643:4706"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"PiotrIndyk, Algorithmic applications of low\u2010distortion geometric embeddings, IEEE Computer Soc., Los Alamitos, CA, 2001, 10\u201333MR1948692","DOI":"10.1109\/SFCS.2001.959878"},{"key":"R22","unstructured":"NathanLinial, Finite metric\u2010spaces\u2014combinatorics, geometry and algorithms, Higher Ed. Press, Beijing, 2002, 573\u20135862003k:05045"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200757"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1007\/BF02773799"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0039-7"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-002-2813-5"},{"key":"R27","unstructured":"I. Newman, Y. Rabinovich, and M. Saks,\n                      Excluded Minors for Embeddings\n                      , unpublished notes."},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(81)90093-9"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"SatishRao, Small distortion and volume preserving embeddings for planar and Euclidean metrics, ACM, New York, 1999, 300\u2013306MR1802217","DOI":"10.1145\/304893.304983"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"R31","unstructured":"AlexanderSchrijver, Homotopic routing methods, Algorithms Combin., Vol. 9, Springer, Berlin, 1990, 329\u201337192f:68139"},{"key":"R32","unstructured":"D. B. Shmoys,\n                      Cut problems and their application to divide\u2010and\u2010conquer\n                      , in Approximation Algorithms for NP\u2010Hard Problems, D. S. Hochbaum, ed., PWS Publishing, Boston, 1997, pp. 192\u2013235."},{"key":"R33","doi-asserted-by":"crossref","unstructured":"MaciejSys\u0142o, AndrzejProskurowski, On Halin graphs, Lecture Notes in Math., Vol. 1018, Springer, Berlin, 1983, 248\u201325686c:05060","DOI":"10.1007\/BFb0071635"},{"key":"R34","volume-title":"Introduction to graph theory","author":"West Douglas","year":"1996"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0895480102417379","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:11:39Z","timestamp":1787321499000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0895480102417379"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1137\/S0895480102417379"],"URL":"https:\/\/doi.org\/10.1137\/s0895480102417379","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]}}}