{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:27:47Z","timestamp":1759638467259},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2011,9,8]],"date-time":"2011-09-08T00:00:00Z","timestamp":1315440000000},"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":[[2012,9]]},"DOI":"10.1007\/s00453-011-9563-9","type":"journal-article","created":{"date-parts":[[2011,9,7]],"date-time":"2011-09-07T21:04:06Z","timestamp":1315429446000},"page":"69-84","source":"Crossref","is-referenced-by-count":5,"title":["Fast Minor Testing in Planar Graphs"],"prefix":"10.1007","volume":"64","author":[{"given":"Isolde","family":"Adler","sequence":"first","affiliation":[]},{"given":"Frederic","family":"Dorn","sequence":"additional","affiliation":[]},{"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[]},{"given":"Ignasi","family":"Sau","sequence":"additional","affiliation":[]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,9,8]]},"reference":[{"key":"9563_CR1","series-title":"LNCS","first-page":"322","volume-title":"Proc. of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT)","author":"I. Adler","year":"2010","unstructured":"Adler, I., Dorn, F., Fomin, F.V., Sau, I., Thilikos, D.M.: Faster parameterized algorithms for minor containment. In: Proc. of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT). LNCS, vol. 6139, pp. 322\u2013333 (2010)"},{"key":"9563_CR2","series-title":"LNCS","first-page":"97","volume-title":"Proc. of the 18th Annual European Symposium on Algorithms (ESA)","author":"I. Adler","year":"2010","unstructured":"Adler, I., Dorn, F., Fomin, F.V., Sau, I., Thilikos, D.M.: Fast minor testing in planar graphs. In: Proc. of the 18th Annual European Symposium on Algorithms (ESA). LNCS, vol. 6346, pp. 97\u2013109 (2010)"},{"key":"9563_CR3","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/s00453-001-0116-5","volume":"33","author":"J. Alber","year":"2002","unstructured":"Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica 33, 461\u2013493 (2002)","journal-title":"Algorithmica"},{"issue":"4","key":"9563_CR4","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N. Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"key":"9563_CR5","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, 153\u2013180 (1994)","journal-title":"J. ACM"},{"issue":"1","key":"9563_CR6","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/s00453-007-9056-z","volume":"51","author":"H.L. Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Grigoriev, A., Koster, A.M.C.A.: Treewidth lower bounds with brambles. Algorithmica 51(1), 81\u201398 (2008)","journal-title":"Algorithmica"},{"issue":"6","key":"9563_CR7","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1145\/1101821.1101823","volume":"52","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M.T., Thilikos, D.M.: Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs. J. ACM 52(6), 866\u2013893 (2005)","journal-title":"J. ACM"},{"key":"9563_CR8","volume-title":"Encyclopedia of Algorithms","author":"E.D. Demaine","year":"2008","unstructured":"Demaine, E.D., Hajiaghayi, M.: Bidimensionality. In: Kao, M.-Y. (ed.) Encyclopedia of Algorithms. Springer, Berlin (2008)"},{"key":"9563_CR9","first-page":"590","volume-title":"Proc. of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Hajiaghayi, M.T.: Bidimensionality: new connections between FPT algorithms and PTASs. In: Proc. of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\u00a0590\u2013601 (2005)"},{"key":"9563_CR10","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1109\/SFCS.2005.14","volume-title":"Proc. of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Hajiaghayi, M.T., Kawarabayashi, K.I.: Algorithmic graph minor theory: decomposition, approximation, and coloring. In: Proc. of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 637\u2013646 (2005)"},{"key":"9563_CR11","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, vol.\u00a0173. Springer, Berlin (2005)"},{"key":"9563_CR12","series-title":"Computer Science Technical Reports","volume-title":"The Feasibility and Use of a Minor Containment Algorithm","author":"M. Dinneen","year":"2000","unstructured":"Dinneen, M., Xiong, L.: The Feasibility and Use of a Minor Containment Algorithm. Computer Science Technical Reports, vol.\u00a0171. University of Auckland, Auckland (2000)"},{"key":"9563_CR13","first-page":"263","volume-title":"Proc. of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS)","author":"F. Dorn","year":"2010","unstructured":"Dorn, F.: Planar subgraph isomorphism revisited. In: Proc. of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 263\u2013274 (2010)"},{"issue":"1","key":"9563_CR14","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/j.cosrev.2008.02.004","volume":"2","author":"F. Dorn","year":"2008","unstructured":"Dorn, F., Fomin, F.V., Thilikos, D.M.: Subexponential parameterized algorithms. Comput. Sci. Rev. 2(1), 29\u201339 (2008)","journal-title":"Comput. Sci. Rev."},{"issue":"3","key":"9563_CR15","doi-asserted-by":"crossref","first-page":"790","DOI":"10.1007\/s00453-009-9296-1","volume":"58","author":"F. Dorn","year":"2010","unstructured":"Dorn, F., Penninkx, E., Bodlaender, H.L., Fomin, F.V.: Efficient exact algorithms on planar graphs: exploiting sphere cut decompositions. Algorithmica 58(3), 790\u2013810 (2010)","journal-title":"Algorithmica"},{"key":"9563_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)"},{"key":"9563_CR17","doi-asserted-by":"crossref","first-page":"769","DOI":"10.1016\/S0022-0000(05)80079-0","volume":"49","author":"M.R. Fellows","year":"1994","unstructured":"Fellows, M.R., Langston, M.A.: On search, decision and the efficiency of polynomial-time algorithms. J. Comput. Syst. Sci. 49, 769\u2013779 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"9563_CR18","volume-title":"Computers and Intractability, a Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, a Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"9563_CR19","series-title":"LNCS","first-page":"984","volume-title":"Proc. of the 20th International Symposium Algorithms and Computation (ISAAC)","author":"Q.-P. Gu","year":"2009","unstructured":"Gu, Q.-P., Tamaki, H.: Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in O(n 1+\u03b5 ) time. In: Proc. of the 20th International Symposium Algorithms and Computation (ISAAC). LNCS, vol. 5878, pp. 984\u2013993 (2009)"},{"key":"9563_CR20","doi-asserted-by":"crossref","unstructured":"Gu, Q.P., Tamaki, H.: Improved bound on the planar branchwidth with respect to the largest grid minor size. Technical report SFU-CMPT-TR 2009-17, Simon Fraiser University, 2009","DOI":"10.1007\/978-3-642-17514-5_8"},{"issue":"1","key":"9563_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/net.10099","volume":"43","author":"I.V. Hicks","year":"2004","unstructured":"Hicks, I.V.: Branch decompositions and minor containment. Networks 43(1), 1\u20139 (2004)","journal-title":"Networks"},{"key":"9563_CR22","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1145\/800119.803896","volume-title":"Proc. of the 6th Annual ACM Symposium on Theory of Computing (STOC)","author":"J.E. Hopcroft","year":"1974","unstructured":"Hopcroft, J.E., Wong, J.K.: Linear time algorithm for isomorphism of planar graphs (preliminary report). In: Proc. of the 6th Annual ACM Symposium on Theory of Computing (STOC), pp. 172\u2013184 (1974)"},{"key":"9563_CR23","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1145\/1536414.1536476","volume-title":"Proc. of the 41st Annual ACM Symposium on Theory of Computing (STOC)","author":"K.I. Kawarabayashi","year":"2009","unstructured":"Kawarabayashi, K.I., Reed, B.A.: Hadwiger\u2019s conjecture is decidable. In: Proc. of the 41st Annual ACM Symposium on Theory of Computing (STOC), pp. 445\u2013454 (2009)"},{"key":"9563_CR24","first-page":"687","volume-title":"Proc. of the 42st Annual ACM Symposium on Theory of Computing (STOC)","author":"K.I. Kawarabayashi","year":"2010","unstructured":"Kawarabayashi, K.I., Wollan, P.: A shorter proof of the graph minor algorithm\u2014the unique linkage theorem. In: Proc. of the 42st Annual ACM Symposium on Theory of Computing (STOC), pp. 687\u2013694 (2010)"},{"key":"9563_CR25","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/3-540-48224-5_36","volume-title":"Proc. of the 28th International Colloquium on Automata, Languages and Programming (ICALP)","author":"Z. Li","year":"2001","unstructured":"Li, Z., Nakano, S.-I.: Efficient generation of plane triangulations without repetitions. In: Proc. of the 28th International Colloquium on Automata, Languages and Programming (ICALP). LNCS, vol.\u00a02076, pp. 433\u2013443 (2001)"},{"key":"9563_CR26","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R.J. Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput. 9, 615\u2013627 (1980)","journal-title":"SIAM J. Comput."},{"key":"9563_CR27","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"B. Mohar","year":"2001","unstructured":"Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins University Press, Baltimore (2001)"},{"issue":"1","key":"9563_CR28","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/S0095-8956(02)00040-0","volume":"88","author":"D. Osthus","year":"2003","unstructured":"Osthus, D., Pr\u00f6mel, H.J., Taraz, A.: On random planar graphs, the number of planar graphs and their triangulations. J. Comb. Theory, Ser. B 88(1), 119\u2013134 (2003)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9563_CR29","first-page":"206","volume-title":"Proc. of the 8th Latin American Symposium on Theoretical Informatics (LATIN)","author":"B.A. Reed","year":"2008","unstructured":"Reed, B.A., Li, Z.: Optimization and recognition for K 5-minor free graphs in linear time. In: Proc. of the 8th Latin American Symposium on Theoretical Informatics (LATIN), pp. 206\u2013215 (2008)"},{"issue":"1","key":"9563_CR30","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.: Graph minors. XIII. The disjoint paths problem. J. Comb. Theory, Ser. B 63(1), 65\u2013110 (1995)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"2","key":"9563_CR31","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1006\/jctb.1994.1073","volume":"62","author":"N. Robertson","year":"1994","unstructured":"Robertson, N., Seymour, P., Thomas, R.: Quickly excluding a planar graph. J. Comb. Theory, Ser. B 62(2), 323\u2013348 (1994)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"2","key":"9563_CR32","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","volume":"92","author":"N. Robertson","year":"2004","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner\u2019s conjecture. J. Comb. Theory, Ser. B 92(2), 325\u2013357 (2004)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9563_CR33","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1007\/978-3-642-14165-2_32","volume-title":"Proc. of the 37th International Colloquium on Automata, Languages and Programming (ICALP)","author":"J. Ru\u00e9","year":"2010","unstructured":"Ru\u00e9, J., Sau, I., Thilikos, D.M.: Dynamic programming for graphs on surfaces. In: Proc. of the 37th International Colloquium on Automata, Languages and Programming (ICALP). LNCS, vol. 6198, pp.\u00a0372\u2013383 (2010)"},{"issue":"1","key":"9563_CR34","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1002\/(SICI)1097-0118(199601)21:1<43::AID-JGT6>3.0.CO;2-M","volume":"21","author":"D.P. Sanders","year":"1998","unstructured":"Sanders, D.P.: On Hamilton cycles in certain planar graphs. J. Graph Theory 21(1), 43\u201350 (1998)","journal-title":"J. Graph Theory"},{"key":"9563_CR35","series-title":"LNCS","first-page":"357","volume-title":"Algorithms\u2014ESA \u201993, Proc. of the First Annual European Symposium","author":"A. Schrijver","year":"1993","unstructured":"Schrijver, A.: Complexity of disjoint paths problems in planar graphs. In: Algorithms\u2014ESA \u201993, Proc. of the First Annual European Symposium. LNCS, vol. 726, pp. 357\u2013359 (1993)"},{"issue":"2","key":"9563_CR36","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"P.D. Seymour","year":"1994","unstructured":"Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica 14(2), 217\u2013241 (1994)","journal-title":"Combinatorica"},{"key":"9563_CR37","doi-asserted-by":"crossref","first-page":"21","DOI":"10.4153\/CJM-1962-002-9","volume":"14","author":"W.T. Tutte","year":"1962","unstructured":"Tutte, W.T.: A census of planar triangulations. Can. J. Math. 14, 21\u201338 (1962)","journal-title":"Can. J. Math."},{"key":"9563_CR38","doi-asserted-by":"crossref","first-page":"378","DOI":"10.2307\/1968197","volume":"32","author":"H. Whitney","year":"1931","unstructured":"Whitney, H.: A theorem on graphs. Ann. Math. 32, 378\u2013390 (1931)","journal-title":"Ann. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9563-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9563-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9563-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,9]],"date-time":"2023-06-09T07:54:54Z","timestamp":1686297294000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9563-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9,8]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,9]]}},"alternative-id":["9563"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9563-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,9,8]]}}}