{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T18:08:57Z","timestamp":1758823737544},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2010,11,1]],"date-time":"2010-11-01T00:00:00Z","timestamp":1288569600000},"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,11]]},"DOI":"10.1007\/s00493-010-2499-x","type":"journal-article","created":{"date-parts":[[2011,3,18]],"date-time":"2011-03-18T20:19:26Z","timestamp":1300479566000},"page":"715-734","source":"Crossref","is-referenced-by-count":2,"title":["Algorithms for finding an induced cycle in planar graphs"],"prefix":"10.1007","volume":"30","author":[{"given":"Ken-ichi","family":"Kawarabayashi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yusuke","family":"Kobayashi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,3,19]]},"reference":[{"key":"2499_CR1","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S. Arnborg","year":"1989","unstructured":"S. Arnborg and A. Proskurowski: Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete Applied Math. 23 (1989), 11\u201324.","journal-title":"Discrete Applied Math"},{"key":"2499_CR2","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0012-365X(91)90098-M","volume":"90","author":"D. Bienstock","year":"1991","unstructured":"D. Bienstock: On the complexity of testing for even holes and induced odd paths, Discrete Math. 90 (1991), 85\u201392.","journal-title":"Discrete Math"},{"key":"2499_CR3","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H. L. Bodlaender","year":"1996","unstructured":"H. L. Bodlaender: A linear time algorithm for finding tree-decompositions of small treewidth, SIAM Journal on Computing 25 (1996), 1305\u20131317.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"2499_CR4","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/s00493-005-0012-8","volume":"25","author":"M. Chudnovsky","year":"2005","unstructured":"M. Chudnovsky, G. Cornu\u00e9jols, X. Liu, P. D. Seymour and K. Vu\u0161kovi\u0107: Recognizing Berge graphs, Combinatorica 25(2) (2005), 143\u2013186.","journal-title":"Combinatorica"},{"key":"2499_CR5","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1002\/jgt.20040","volume":"48","author":"M. Chudnovsky","year":"2005","unstructured":"M. Chudnovsky, K. Kawarabayashi and P. D. Seymour: Detecting even holes, Journal of Graph Theory 48 (2005), 85\u2013111.","journal-title":"Journal of Graph Theory"},{"key":"2499_CR6","doi-asserted-by":"crossref","first-page":"51","DOI":"10.4007\/annals.2006.164.51","volume":"64","author":"M. Chudnovsky","year":"2006","unstructured":"M. Chudnovsky, N. Robertson, P. D. Seymour and R. Thomas: The strong perfect graph theorem, Annals of Mathematics 64 (2006), 51\u2013219.","journal-title":"Annals of Mathematics"},{"key":"2499_CR7","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1002\/jgt.10006","volume":"39","author":"M. Conforti","year":"2002","unstructured":"M. Conforti, G. Cornu\u00e9jols, A. Kapoor and K. Vu\u0161kovi\u0107: Even-hole-free graphs. I. Decomposition theorem; Journal of Graph Theory 39 (2002), 6\u201349.","journal-title":"Journal of Graph Theory"},{"key":"2499_CR8","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1002\/jgt.10045","volume":"40","author":"M. Conforti","year":"2002","unstructured":"M. Conforti, G. Cornu\u00e9jols, A. Kapoor and K. Vu\u0161kovi\u0107: Even-hole-free graphs, II. Recognition algorithm; Journal of Graph Theory 40 (2002), 238\u2013266.","journal-title":"Journal of Graph Theory"},{"key":"2499_CR9","first-page":"1","volume":"89","author":"M. R. Fellows","year":"1987","unstructured":"M. R. Fellows: The Robertson-Seymour Theorems: a survey of applications; in: Comtemporary Mathematics, Vol. 89, pp. 1\u201318, American Mathematical Society, 1987.","journal-title":"Comtemporary Mathematics"},{"key":"2499_CR10","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1007\/BF01190507","volume":"13","author":"M. R. Fellows","year":"1995","unstructured":"M. R. Fellows, J. Kratochvil, M. Middendorf and F. Pfeiffer: The complexity of induced minors and related problems, Algorithmica 13 (1995), 266\u2013282.","journal-title":"Algorithmica"},{"key":"2499_CR11","unstructured":"K. Kawarabayashi and Y. Kobayashi: A linear time algorithm for the induced disjoint paths problem in planar graphs, manuscript."},{"key":"2499_CR12","doi-asserted-by":"crossref","unstructured":"K. Kawarabayashi and Y. Kobayashi: The induced disjoint paths problem, in: Proceedings of the 13th Integer Programming and Combinatorial Optimization Conference (LNCS 5035), 2008, pp. 47\u201361.","DOI":"10.1007\/978-3-540-68891-4_4"},{"key":"2499_CR13","doi-asserted-by":"crossref","first-page":"3231","DOI":"10.1016\/j.dam.2009.06.020","volume":"157","author":"Y. Kobayashi","year":"2009","unstructured":"Y. Kobayashi: Induced disjoint paths problem in a planar digraph, Discrete Applied Math. 157 (2009), pp. 3231\u20133238.","journal-title":"Discrete Applied Math"},{"key":"2499_CR14","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1006\/jctb.1994.1011","volume":"60","author":"C. McDiarmid","year":"1994","unstructured":"C. McDiarmid, B. Reed, A. Schrijver and B. Shepherd: Induced circuits in planar graphs, Journal of Combinatorial Theory Ser. B 60 (1994), 169\u2013176.","journal-title":"Journal of Combinatorial Theory Ser. B"},{"key":"2499_CR15","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"B. Mohar","year":"2001","unstructured":"B. Mohar and C. Thomassen: Graphs on Surfaces, The Johns Hopkins University Press, Baltimore and London, 2001."},{"key":"2499_CR16","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/0166-218X(94)00104-L","volume":"57","author":"B. Reed","year":"1995","unstructured":"B. Reed: Rooted routing in the plane, Discrete Applied Math. 57 (1995), 213\u2013227.","journal-title":"Discrete Applied Math"},{"key":"2499_CR17","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1090\/conm\/147\/01180","volume":"147","author":"B. A. Reed","year":"1993","unstructured":"B. A. Reed, N. Robertson, A. Schrijver and P. D. Seymour: Finding disjoint trees in planar graphs in linear time, in: Contemporary Mathematics, Vol. 147, pp. 295\u2013301, American Mathematical Society, 1993.","journal-title":"Contemporary Mathematics"},{"key":"2499_CR18","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1016\/0095-8956(88)90070-6","volume":"45","author":"N. Robertson","year":"1988","unstructured":"N. Robertson and P. D. Seymour: Graph minors, VII. Disjoint paths on a surface; Journal of Combinatorial Theory Ser. B 45 (1988), 212\u2013254.","journal-title":"Journal of Combinatorial Theory Ser. B"},{"key":"2499_CR19","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1006\/jctb.1994.1007","volume":"60","author":"N. Robertson","year":"1994","unstructured":"N. Robertson and P. D. Seymour: Graph minors, XI. Circuits on a surface; Journal of Combinatorial Theory Ser. B 60 (1994), 72\u2013106.","journal-title":"Journal of Combinatorial Theory Ser. B"},{"key":"2499_CR20","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"N. Robertson and P. D. Seymour: Graph minors, XIII. The disjoint paths problem; Journal of Combinatorial Theory Ser. B 63 (1995), 65\u2013110.","journal-title":"Journal of Combinatorial Theory Ser. B"},{"key":"2499_CR21","unstructured":"N. Robertson and P. D. Seymour: Graph minors. XXII. Irrelevant vertices in linkage problems, manuscript."},{"key":"2499_CR22","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1006\/jctb.1994.1073","volume":"62","author":"N. Robertson","year":"1994","unstructured":"N. Robertson, P. D. Seymour and R. Thomas: Quickly excluding a planar graph, Journal of Combinatorial Theory Ser. B 62 (1994), 323\u2013348.","journal-title":"Journal of Combinatorial Theory Ser. B"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-010-2499-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-010-2499-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-010-2499-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T09:16:52Z","timestamp":1712308612000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-010-2499-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11]]},"references-count":22,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["2499"],"URL":"https:\/\/doi.org\/10.1007\/s00493-010-2499-x","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,11]]}}}