{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:34:35Z","timestamp":1764783275656,"version":"3.38.0"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2010,9,1]],"date-time":"2010-09-01T00:00:00Z","timestamp":1283299200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2010,9]]},"DOI":"10.1007\/s00493-010-2341-5","type":"journal-article","created":{"date-parts":[[2011,3,25]],"date-time":"2011-03-25T21:24:05Z","timestamp":1301088245000},"page":"533-552","source":"Crossref","is-referenced-by-count":15,"title":["Approximation algorithms via contraction decomposition"],"prefix":"10.1007","volume":"30","author":[{"given":"Erik D.","family":"Demaine","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MohammadTaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bojan","family":"Mohar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,3,13]]},"reference":[{"key":"2341_CR1","unstructured":"Sanjeev Arora, Michelangelo Grigni, David Karger, Philip Klein and Andrzej Woloszyn: A polynomial-time approximation scheme for weighted planar graph TSP, in: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 33\u201341, 1998."},{"key":"2341_CR2","first-page":"7","volume-title":"Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence (UAI-2001)","author":"E. Amir","year":"2001","unstructured":"Eyal Amir: Efficient approximation for triangulation of minimum treewidth, in: Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence (UAI-2001), pages 7\u201315, Morgan Kaufmann Publishers, San Francisco, CA, 2001."},{"key":"2341_CR3","doi-asserted-by":"crossref","unstructured":"Sanjeev Arora, Satish Rao and Umesh Vazirani: Expander flows, geometric embeddings and graph partitioning; in: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 222\u2013231, 2004.","DOI":"10.1145\/1007352.1007355"},{"issue":"1","key":"2341_CR4","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B. S. Baker","year":"1994","unstructured":"Brenda S. Baker: Approximation algorithms for NP-complete problems on planar graphs, Journal of the Association for Computing Machinery 41(1) (1994), 153\u2013180.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"2341_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1007\/11561071_43","volume-title":"Proceedings of the 13th Annual European Symposium on Algorithms","author":"A. Berger","year":"2005","unstructured":"Andr\u00e9 Berger, Artur Czumaj, Michelangelo Grigni and Hairong Zhao: Approximation schemes for minimum 2-connected spanning subgraphs in weighted planar graphs, in: Proceedings of the 13th Annual European Symposium on Algorithms, volume 3669 of Lecture Notes in Computer Science, pages 472\u2013483, Palma de Mallorca, Spain, October 2005."},{"issue":"2","key":"2341_CR6","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1006\/jctb.1996.0016","volume":"66","author":"R. Brunet","year":"1996","unstructured":"Richard Brunet, Bojan Mohar and R. Bruce Richter: Separating and non-separating disjoint homotopic cycles in graph embeddings, Journal of Combinatorial Theory, Series B 66(2) (1996), 201\u2013231.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"2341_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-540-30577-4_1","volume-title":"Proceedings of the 31st Conference on Current Trends in Theory and Practice of Computer Science","author":"H. L. Bodlaender","year":"2005","unstructured":"Hans L. Bodlaender: Discovering treewidth, in: Proceedings of the 31st Conference on Current Trends in Theory and Practice of Computer Science, volume 3381 of Lecture Notes in Computer Science, pages 1\u201316, Liptovsk\u00fd J\u00e1n, Slovakia, January 2005."},{"key":"2341_CR8","first-page":"496","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"A. Czumaj","year":"2004","unstructured":"Artur Czumaj, Michelangelo Grigni, Papa Sissokho and Hairong Zhao: Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs, in: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 496\u2013505, Society for Industrial and Applied Mathematics. Philadelphia, PA, USA, 2004."},{"key":"2341_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/11561071_14","volume-title":"Proceedings of the 13th Annual European Symposium on Algorithms","author":"S. Cabello","year":"2005","unstructured":"Sergio Cabello and Bojan Mohar: Finding shortest non-separating and non-contractible cycles for topologically embedded graphs, in: Proceedings of the 13th Annual European Symposium on Algorithms, volume 3669 of Lecture Notes in Computer Science, pages 131\u2013142, Palma de Mallorca, Spain, October 2005."},{"issue":"1","key":"2341_CR10","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.jctb.2003.09.001","volume":"91","author":"M. DeVos","year":"2004","unstructured":"Matt DeVos, Guoli Ding, Bogdan Oporowski, Daniel P. Sanders, Bruce Reed, Paul Seymour and Dirk Vertigan: Excluding any graph as a minor allows a low tree-width 2-coloring, Journal of Combinatorial Theory, Series B 91(1) (2004), 25\u201341.","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"3","key":"2341_CR11","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1137\/S0895480103433410","volume":"18","author":"E. D. Demaine","year":"2004","unstructured":"Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos: Bidimensional parameters and local treewidth, SIAM Journal on Discrete Mathematics 18(3) (2004), 501\u2013511.","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"1","key":"2341_CR12","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1145\/1077464.1077468","volume":"1","author":"E. D. Demaine","year":"2005","unstructured":"Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos: Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs, ACM Transactions on Algorithms 1(1) (2005), 33\u201347.","journal-title":"ACM Transactions on Algorithms"},{"issue":"6","key":"2341_CR13","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1145\/1101821.1101823","volume":"52","author":"E. D. Demaine","year":"2005","unstructured":"Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos: Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs, Journal of the ACM 52(6) (2005), 866\u2013893.","journal-title":"Journal of the ACM"},{"key":"2341_CR14","doi-asserted-by":"crossref","unstructured":"Frederic Dorn, Fedor V. Fomin and Dimitrios M. Thilikos: Fast subexponential algorithm for non-local problems on graphs of bounded genus, in: Proceedings of the 10th Scandinavian Workshop on Algorithm Theory, volume 4059 of Lecture Notes in Computer Science, pages 172\u2013183, Riga, Latvia, July 2006.","DOI":"10.1007\/11785293_18"},{"issue":"3","key":"2341_CR15","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/s00453-004-1106-1","volume":"40","author":"E. D. Demaine","year":"2004","unstructured":"Erik D. Demaine and MohammadTaghi Hajiaghayi: Diameter and treewidth in minor-closed graph families, revisited; Algorithmica 40(3) (2004), 211\u2013215.","journal-title":"Algorithmica"},{"key":"2341_CR16","unstructured":"Erik D. Demaine and MohammadTaghi Hajiaghayi: Equivalence of local treewidth and linear local treewidth and its algorithmic applications, in: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904), pages 833\u2013842, January 2004."},{"key":"2341_CR17","doi-asserted-by":"crossref","unstructured":"Erik D. Demaine, MohammadTaghi Hajiaghayi and Ken-Ichi Kawarabayashi: Algorithmic graph minor theory: Decomposition, approximation, and coloring; in: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pages 637\u2013646, Pittsburgh, PA, October 2005.","DOI":"10.1109\/SFCS.2005.14"},{"issue":"2","key":"2341_CR18","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/j.jcss.2003.12.001","volume":"69","author":"E. D. Demaine","year":"2004","unstructured":"Erik D. Demaine, MohammadTaghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde and Dimitrios M. Thilikos: Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, Journal of Computer and System Sciences 69(2) (2004), 166\u2013195.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"2341_CR19","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1137\/040616929","volume":"20","author":"E. D. Demaine","year":"2006","unstructured":"Erik D. Demaine, MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos: The bidimensional theory of bounded-genus graphs, SIAM Journal on Discrete Mathematics 20(2) (2006), 357\u2013371.","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"3\u20134","key":"2341_CR20","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/s004530010020","volume":"27","author":"D. Eppstein","year":"2000","unstructured":"David Eppstein: Diameter and treewidth in minor-closed graph families, Algorithmica 27(3\u20134) (2000), 275\u2013291.","journal-title":"Algorithmica"},{"issue":"2","key":"2341_CR21","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1006\/jcss.1998.1587","volume":"57","author":"U. Feige","year":"1998","unstructured":"Uriel Feige and Joe Kilian: Zero knowledge and the chromatic number, Journal of Computer and System Sciences 57(2) (1998), 187\u2013199.","journal-title":"Journal of Computer and System Sciences"},{"key":"2341_CR22","doi-asserted-by":"crossref","unstructured":"Fedor V. Fomin and Dimitrios M. Thilikos: Fast parameterized algorithms for graphs on surfaces: Linear kernel and exponential speed-up, in: Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP 2004), pages 581\u2013592, Turku, Finland, July 2004.","DOI":"10.1007\/978-3-540-27836-8_50"},{"issue":"3","key":"2341_CR23","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1016\/0196-6774(84)90019-1","volume":"5","author":"J. R. Gilbert","year":"1984","unstructured":"John R. Gilbert, Joan P. Hutchinson and Robert Endre Tarjan: A separator theorem for graphs of bounded genus, J. Algorithms 5(3) (1984), 391\u2013407.","journal-title":"J. Algorithms"},{"key":"2341_CR24","doi-asserted-by":"crossref","unstructured":"Michelangelo Grigni, Elias Koutsoupias and Christos Papadimitriou: An approximation scheme for planar graph TSP, in: Proceedings of the 36th Annual Symposium on Foundations of Computer Science (Milwaukee, WI, 1995), pages 640\u2013645, Los Alamitos, CA, 1995.","DOI":"10.1109\/SFCS.1995.492665"},{"key":"2341_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1007\/3-540-45022-X_73","volume-title":"Proceedings of the 27th International Colloquium of Automata, Languages and Programming (Geneva, 2000)","author":"M. Grigni","year":"2000","unstructured":"Michelangelo Grigni: Approximate TSP in graphs with forbidden minors, in: Proceedings of the 27th International Colloquium of Automata, Languages and Programming (Geneva, 2000), volume 1853 of Lecture Notes in Computer Science, pages 869\u2013877. Springer, Berlin, 2000."},{"issue":"4","key":"2341_CR26","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1007\/s00493-003-0037-9","volume":"23","author":"M. Grohe","year":"2003","unstructured":"Martin Grohe: Local tree-width, excluded minors, and approximation algorithms; Combinatorica 23(4) (2003), 613\u2013632.","journal-title":"Combinatorica"},{"key":"2341_CR27","unstructured":"Michelangelo Grigni and Papa Sissokho: Light spanners and approximate TSP in weighted graphs with forbidden minors, in: Proceedings of the 13th Annual ACMSIAM Symposium on Discrete Algorithms, pages 852\u2013857, 2002."},{"issue":"4","key":"2341_CR28","doi-asserted-by":"crossref","first-page":"882","DOI":"10.1137\/S0097539705447244","volume":"35","author":"J. A. Kelner","year":"2006","unstructured":"Jonathan A. Kelner: Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus; SIAM Journal on Computing 35(4) (2006), 882\u2013902 (electronic).","journal-title":"SIAM Journal on Computing"},{"key":"2341_CR29","unstructured":"Philip N. Klein: A linear-time approximation scheme for TSP for planar weighted graphs, in: Proceedings of the 46th IEEE Symposium on Foundations of Computer Science, pages 146\u2013155, 2005."},{"key":"2341_CR30","doi-asserted-by":"crossref","unstructured":"Philip N. Klein: A subset spanner for planar graphs, with application to subset TSP, in: Proceedings of the 38th ACM Symposium on Theory of Computing, pages 749\u2013756, Seattle, WA, 2006.","DOI":"10.1145\/1132516.1132620"},{"issue":"6","key":"2341_CR31","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"T. Leighton","year":"1999","unstructured":"Tom Leighton and Satish Rao: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM 46(6) (1999), 787\u2013832.","journal-title":"Journal of the ACM"},{"issue":"3","key":"2341_CR32","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R. J. Lipton","year":"1980","unstructured":"Richard J. Lipton and Robert Endre Tarjan: Applications of a planar separator theorem, SIAM Journal on Computing 9(3) (1980), 615\u2013627.","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"2341_CR33","doi-asserted-by":"crossref","first-page":"1272","DOI":"10.4153\/CJM-1992-076-8","volume":"44","author":"B. Mohar","year":"1992","unstructured":"Bojan Mohar: Combinatorial local planarity and the width of graph embeddings, Canadian Journal of Mathematics 44(6) (1992), 1272\u20131288.","journal-title":"Canadian Journal of Mathematics"},{"issue":"1","key":"2341_CR34","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1137\/S089548019529248X","volume":"12","author":"B. Mohar","year":"1999","unstructured":"Bojan Mohar: A linear time algorithm for embedding graphs in an arbitrary surface, SIAM Journal on Discrete Mathematics 12(1) (1999), 6\u201326.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"2341_CR35","series-title":"London Math. Soc. Lecture Note Ser.","first-page":"145","volume-title":"Surveys in Combinatorics","author":"B. Mohar","year":"2001","unstructured":"Bojan Mohar: Graph minors and graphs on surfaces, in: Surveys in Combinatorics, volume 288 of London Math. Soc. Lecture Note Ser., pages 145\u2013163. Cambridge Univ. Press, Cambridge, 2001."},{"key":"2341_CR36","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on surfaces","author":"B. Mohar","year":"2001","unstructured":"Bojan Mohar and Carsten Thomassen: Graphs on surfaces, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2001."},{"issue":"3","key":"2341_CR37","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Neil Robertson and Paul D. Seymour: Graph minors II.: Algorithmic aspects of tree-width; Journal of Algorithms 7(3) (1986), 309\u2013322.","journal-title":"Journal of Algorithms"},{"issue":"1","key":"2341_CR38","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1006\/jctb.1994.1007","volume":"60","author":"N. Robertson","year":"1994","unstructured":"Neil Robertson and Paul D. Seymour: Graph minors XI.: Circuits on a surface; Journal of Combinatorial Theory, Series B 60(1) (1994), 72\u2013106.","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"1","key":"2341_CR39","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0095-8956(03)00042-X","volume":"89","author":"N. Robertson","year":"2003","unstructured":"Neil Robertson and Paul D. Seymour: Graph minors XVI.: Excluding a non-planar graph; Journal of Combinatorial Theory, Series B 89(1) (2003), 43\u201376.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"2341_CR40","unstructured":"Robin Thomas: Problem Session of the 3rd Solvene Conference on Graph Theory, Bled, Slovenia, 1995."},{"issue":"2","key":"2341_CR41","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1006\/inco.1997.2697","volume":"142","author":"M. Thorup","year":"1998","unstructured":"Mikkel Thorup: All structured programs have small tree-width and good register allocation, Information and Computation 142(2) (1998), 159\u2013181.","journal-title":"Information and Computation"},{"key":"2341_CR42","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1007\/BF01594196","volume":"114","author":"K. Wagner","year":"1937","unstructured":"Klaus Wagner: \u00dcber eine Eigenschaft der ebenen Komplexe, Mathematische Annalen 114 (1937), 570\u2013590.","journal-title":"Mathematische Annalen"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-010-2341-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-010-2341-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-010-2341-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T18:04:40Z","timestamp":1741111480000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-010-2341-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":42,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["2341"],"URL":"https:\/\/doi.org\/10.1007\/s00493-010-2341-5","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[2010,9]]}}}