{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,24]],"date-time":"2026-04-24T04:56:38Z","timestamp":1777006598504,"version":"3.51.4"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2010,6,25]],"date-time":"2010-06-25T00:00:00Z","timestamp":1277424000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,9]]},"DOI":"10.1007\/s00453-010-9423-z","type":"journal-article","created":{"date-parts":[[2010,6,24]],"date-time":"2010-06-24T13:53:25Z","timestamp":1277387605000},"page":"141-160","source":"Crossref","is-referenced-by-count":2,"title":["k-Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees"],"prefix":"10.1007","volume":"61","author":[{"given":"Yuval","family":"Emek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,6,25]]},"reference":[{"key":"9423_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Bartal, Y., Neiman, O.: Nearly tight low stretch spanning trees. In: Proc. 49th IEEE Symp. on Foundations of Computer Science (FOCS), 2008","DOI":"10.1109\/FOCS.2008.62"},{"key":"9423_CR2","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1137\/S0097539792224474","volume":"24","author":"N. Alon","year":"1995","unstructured":"Alon, N., Karp, R.M., Peleg, D., West, D.: A graph-theoretic game and its application to the k-server problem. SIAM J. Comput. 24, 78\u2013100 (1995)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9423_CR3","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153\u2013180 (1994)","journal-title":"J. ACM"},{"key":"9423_CR4","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: Probabilistic approximations of metric spaces and its algorithmic applications. In: Proc. 37th IEEE Symp. on Foundations of Computer Science (FOCS), pp.\u00a0184\u2013193 (1996)","DOI":"10.1109\/SFCS.1996.548477"},{"key":"9423_CR5","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: On approximating arbitrary metrics by tree metrics. In: Proc. 30th ACM Symp. on the Theory of Computing (STOC), pp.\u00a0161\u2013168 (1998)","DOI":"10.1145\/276698.276725"},{"key":"9423_CR6","doi-asserted-by":"crossref","unstructured":"Charikar, M., Chekuri, C., Goel, A., Guha, S., Plotkin, S.A.: Approximating a finite metric by a small number of tree metrics. In: Proc. 39th Symp. on Foundations of Computer Science (FOCS), pp.\u00a0379\u2013388 (1998)","DOI":"10.1109\/SFCS.1998.743488"},{"issue":"1","key":"9423_CR7","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1137\/S0895480102417379","volume":"20","author":"C. Chekuri","year":"2006","unstructured":"Chekuri, C., Gupta, A., Newman, I., Rabinovich, Y., Sinclair, A.: Embedding k-outerplanar graphs into \u2113 1. SIAM J. Discrete Math. 20(1), 119\u2013136 (2006)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"9423_CR8","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1137\/050641661","volume":"38","author":"M. Elkin","year":"2008","unstructured":"Elkin, M., Emek, Y., Spielman, D.A., Teng, S.-H.: Lower-stretch spanning trees. SIAM J. Comput. 38(2), 608\u2013628 (2008)","journal-title":"SIAM J. Comput."},{"key":"9423_CR9","doi-asserted-by":"crossref","unstructured":"Emek, Y., Peleg, D.: A tight upper bound on the probabilistic embedding of series-parallel graphs. In: Proc. 17th ACM-SIAM Symp. on Discrete algorithm (SODA), pp. 1045\u20131053 (2006)","DOI":"10.1145\/1109557.1109673"},{"issue":"3","key":"9423_CR10","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1016\/j.jcss.2004.04.011","volume":"69","author":"J. Fakcharoenphol","year":"2004","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69(3), 485\u2013497 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"9423_CR11","volume-title":"Handbook of Combinatorics, vol. 1","year":"1995","unstructured":"Graham, R.L., Gr\u00f6tschel, M., Lov\u00e1sz, L. (eds.): Handbook of Combinatorics, vol. 1. MIT Press, Cambridge (1995)"},{"issue":"2","key":"9423_CR12","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/s00493-004-0015-x","volume":"24","author":"A. Gupta","year":"2004","unstructured":"Gupta, A., Newman, I., Rabinovich, Y., Sinclair, A.: Cuts, trees and \u2113 1-embeddings of graphs. Combinatorica 24(2), 233\u2013269 (2004)","journal-title":"Combinatorica"},{"issue":"3","key":"9423_CR13","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1007\/BF01363288","volume":"156","author":"R. Halin","year":"1964","unstructured":"Halin, R.: \u00dcber simpliziale Zerf\u00e4llungen beliebiger (endlicher oder unendlicher) Graphen. Math. Ann. 156(3), 216\u2013225 (1964)","journal-title":"Math. Ann."},{"key":"9423_CR14","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1137\/0203015","volume":"3","author":"T.C. Hu","year":"1974","unstructured":"Hu, T.C.: Optimum communication spanning trees. SIAM J. Comput. 3, 188\u2013195 (1974)","journal-title":"SIAM J. Comput."},{"key":"9423_CR15","doi-asserted-by":"crossref","unstructured":"Indyk, P., Sidiropoulos, A.: Probabilistic embeddings of bounded genus graphs into planar graphs. In: Proc. 23rd ACM Symp. on Computational Geometry (SoCG), pp.\u00a0204\u2013209 (2007)","DOI":"10.1145\/1247069.1247107"},{"key":"9423_CR16","doi-asserted-by":"crossref","unstructured":"Klein, P.N., Plotkin, S.A., Rao, S.: Excluded minors, network decomposition, and multicommodity flow. In: Proc. 25th ACM Symp. on Theory of Computing (STOC), pp.\u00a0682\u2013690 (1993)","DOI":"10.1145\/167088.167261"},{"issue":"4","key":"9423_CR17","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/S0020-0190(01)00161-2","volume":"80","author":"G. Konjevod","year":"2001","unstructured":"Konjevod, G., Ravi, R., Salman, F.S.: On approximating planar metrics by tree metrics. Inf. Process. Lett. 80(4), 213\u2013219 (2001)","journal-title":"Inf. Process. Lett."},{"key":"9423_CR18","doi-asserted-by":"crossref","first-page":"509","DOI":"10.2307\/2371182","volume":"57","author":"H. Whitney","year":"1935","unstructured":"Whitney, H.: On the abstract properties of linear dependence. Am. J. Math. 57, 509\u2013533 (1935)","journal-title":"Am. J. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9423-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9423-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9423-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T06:24:28Z","timestamp":1740205468000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9423-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,25]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["9423"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9423-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,6,25]]}}}