{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:57:31Z","timestamp":1725537451619},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642041273"},{"type":"electronic","value":"9783642041280"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04128-0_18","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T18:16:36Z","timestamp":1252952196000},"page":"203-214","source":"Crossref","is-referenced-by-count":0,"title":["k-Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees"],"prefix":"10.1007","author":[{"given":"Yuval","family":"Emek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Bartal, Y., Neiman, O.: Nearly tight low stretch spanning trees. In: 49th IEEE Symp. on Foundations of Computer Science (FOCS), pp. 781\u2013790 (2008)","DOI":"10.1109\/FOCS.2008.62"},{"key":"18_CR2","doi-asserted-by":"publisher","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.\u00a024, 78\u2013100 (1995)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"18_CR3","doi-asserted-by":"publisher","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\u00a041(1), 153\u2013180 (1994)","journal-title":"J. ACM"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: Probabilistic approximations of metric spaces and its algorithmic applications. In: 37th IEEE Symp. on Foundations of Computer Science (FOCS), pp. 184\u2013193 (1996)","DOI":"10.1109\/SFCS.1996.548477"},{"key":"18_CR5","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: On approximating arbitrary metrics by tree metrics. In: 30th ACM Symp. on the Theory of Computing (STOC), pp. 161\u2013168 (1998)","DOI":"10.1145\/276698.276725"},{"key":"18_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: 39th Symp. on Foundations of Computer Science (FOCS), pp. 379\u2013388 (1998)","DOI":"10.1109\/SFCS.1998.743488"},{"issue":"1","key":"18_CR7","doi-asserted-by":"publisher","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 \u21131. SIAM J. Discrete Math.\u00a020(1), 119\u2013136 (2006)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"18_CR8","doi-asserted-by":"publisher","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.\u00a038(2), 608\u2013628 (2008)","journal-title":"SIAM J. Comput."},{"key":"18_CR9","unstructured":"Emek, Y.: k-Outerplanar graphs, planar duality, and low stretch spanning trees, \n                    \n                      http:\/\/www.eng.tau.ac.il\/~yuvale\/Publications\/k-outerplanar.pdf"},{"key":"18_CR10","doi-asserted-by":"crossref","unstructured":"Emek, Y., Peleg, D.: A tight upper bound on the probabilistic embedding of series-parallel graphs. In: 17th ACM-SIAM Symp. on Discrete algorithm (SODA), pp. 1045\u20131053 (2006)","DOI":"10.1145\/1109557.1109673"},{"issue":"3","key":"18_CR11","doi-asserted-by":"publisher","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.\u00a069(3), 485\u2013497 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"18_CR12","doi-asserted-by":"publisher","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 \u21131-embeddings of graphs. Combinatorica\u00a024(2), 233\u2013269 (2004)","journal-title":"Combinatorica"},{"key":"18_CR13","doi-asserted-by":"publisher","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.\u00a03, 188\u2013195 (1974)","journal-title":"SIAM J. Comput."},{"key":"18_CR14","doi-asserted-by":"crossref","unstructured":"Indyk, P., Sidiropoulos, A.: Probabilistic embeddings of bounded genus graphs into planar graphs. In: 23rd ACM Symp. on Computational Geometry (SoCG), pp. 204\u2013209 (2007)","DOI":"10.1145\/1247069.1247107"},{"key":"18_CR15","doi-asserted-by":"crossref","unstructured":"Klein, P.N., Plotkin, S.A., Rao, S.: Excluded minors, network decomposition, and multicommodity flow. In: 25th ACM Symp. on Theory of Computing (STOC), pp. 682\u2013690 (1993)","DOI":"10.1145\/167088.167261"},{"issue":"4","key":"18_CR16","doi-asserted-by":"publisher","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.\u00a080(4), 213\u2013219 (2001)","journal-title":"Inf. Process. Lett."},{"key":"18_CR17","doi-asserted-by":"publisher","first-page":"509","DOI":"10.2307\/2371182","volume":"57","author":"H. Whitney","year":"1935","unstructured":"Whitney, H.: On the abstract properties of linear dependence. Amer. J. Math.\u00a057, 509\u2013533 (1935)","journal-title":"Amer. J. Math."}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04128-0_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,9]],"date-time":"2019-03-09T20:01:29Z","timestamp":1552161689000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04128-0_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642041273","9783642041280"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04128-0_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}