{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:15:31Z","timestamp":1725563731446},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642157745"},{"type":"electronic","value":"9783642157752"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15775-2_9","type":"book-chapter","created":{"date-parts":[[2010,9,1]],"date-time":"2010-09-01T14:47:32Z","timestamp":1283352452000},"page":"97-109","source":"Crossref","is-referenced-by-count":3,"title":["Fast Minor Testing in Planar Graphs"],"prefix":"10.1007","author":[{"given":"Isolde","family":"Adler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frederic","family":"Dorn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ignasi","family":"Sau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"9_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1007\/978-3-642-13731-0_31","volume-title":"SWAT 2010","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: Kaplan, H. (ed.) SWAT 2010. LNCS, vol.\u00a06139, pp. 322\u2013333. Springer, Heidelberg (2010)"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Adler, I., Dorn, F., Fomin, F.V., Sau, I., Thilikos, D.M.: Fast Minor Testing in Planar Graphs (2010), http:\/\/users.uoa.gr\/~sedthilk\/papers\/fastminorch.pdf","DOI":"10.1007\/978-3-642-15775-2_9"},{"key":"9_CR3","doi-asserted-by":"publisher","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\u00a033, 461\u2013493 (2002)","journal-title":"Algorithmica"},{"key":"9_CR4","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. Journal of the ACM\u00a041, 153\u2013180 (1994)","journal-title":"Journal of the ACM"},{"issue":"6","key":"9_CR5","doi-asserted-by":"publisher","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. Journal of the ACM\u00a052(6), 866\u2013893 (2005)","journal-title":"Journal of the ACM"},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Hajiaghayi, M.: Bidimensionality. In: Kao, M.-Y. (ed.) Encyclopedia of Algorithms. Springer, Heidelberg (2008)","DOI":"10.1007\/978-0-387-30162-4_47"},{"key":"9_CR7","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. 590\u2013601 (2005)"},{"key":"9_CR8","doi-asserted-by":"crossref","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)","DOI":"10.1109\/SFCS.2005.14"},{"key":"9_CR9","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, vol.\u00a0173. Springer, Heidelberg (2005)"},{"key":"9_CR10","unstructured":"Dinneen, M., Xiong, L.: The Feasibility and Use of a Minor Containment Algorithm. Computer Science Technical Reports 171, University of Auckland (2000)"},{"key":"9_CR11","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":"9_CR12","doi-asserted-by":"publisher","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. Computer Science Review\u00a02(1), 29\u201339 (2008)","journal-title":"Computer Science Review"},{"key":"9_CR13","doi-asserted-by":"crossref","unstructured":"Dorn, F., Penninkx, E., Bodlaender, H.L., Fomin, F.V.: Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions. Algorithmica (2009) (to appear)","DOI":"10.1007\/s00453-009-9296-1"},{"key":"9_CR14","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, Heidelberg (1999)"},{"key":"9_CR15","doi-asserted-by":"publisher","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. Comp. Syst. Sc.\u00a049, 769\u2013779 (1994)","journal-title":"J. Comp. Syst. Sc."},{"key":"9_CR16","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. W.H. Freeman and Company, New York (1979)"},{"key":"9_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"984","DOI":"10.1007\/978-3-642-10631-6_99","volume-title":"Algorithms and Computation","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\u2009+\u2009\u03b5 ) time. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol.\u00a05878, pp. 984\u2013993. Springer, Heidelberg (2009)"},{"key":"9_CR18","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":"9_CR19","doi-asserted-by":"publisher","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\u00a043(1), 1\u20139 (2004)","journal-title":"Networks"},{"key":"9_CR20","doi-asserted-by":"crossref","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)","DOI":"10.1145\/1536414.1536476"},{"key":"9_CR21","unstructured":"Kawarabayashi, K.i., Wollan, P.: A shorter proof of the Graph Minor Algorithm - The Unique Linkage Theorem. In: Proc. of the 42st Annual ACM Symposium on Theory of Computing, STOC (to appear, 2010)"},{"key":"9_CR22","doi-asserted-by":"publisher","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.\u00a09, 615\u2013627 (1980)","journal-title":"SIAM J. Comput."},{"key":"9_CR23","doi-asserted-by":"crossref","unstructured":"Mohar, B., Thomassen, C.: Graphs on surfaces. John Hopkins University Press (2001)","DOI":"10.56021\/9780801866890"},{"issue":"1","key":"9_CR24","doi-asserted-by":"publisher","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\u00a088(1), 119\u2013134 (2003)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9_CR25","doi-asserted-by":"crossref","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)","DOI":"10.1007\/978-3-540-78773-0_18"},{"issue":"1","key":"9_CR26","doi-asserted-by":"publisher","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\u00a063(1), 65\u2013110 (1995)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"2","key":"9_CR27","doi-asserted-by":"publisher","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\u00a062(2), 323\u2013348 (1994)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"2","key":"9_CR28","doi-asserted-by":"publisher","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\u00a092(2), 325\u2013357 (2004)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9_CR29","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 (to appear, 2010), http:\/\/hal.archives-ouvertes.fr\/inria-00443582"},{"issue":"2","key":"9_CR30","doi-asserted-by":"publisher","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\u00a014(2), 217\u2013241 (1994)","journal-title":"Combinatorica"},{"key":"9_CR31","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. Canadian Journal of Mathematics\u00a014, 21\u201338 (1962)","journal-title":"Canadian Journal of Mathematics"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15775-2_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,3]],"date-time":"2023-06-03T03:15:31Z","timestamp":1685762131000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15775-2_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642157745","9783642157752"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15775-2_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}