{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T17:25:16Z","timestamp":1784568316617,"version":"3.55.0"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2011,1,8]],"date-time":"2011-01-08T00:00:00Z","timestamp":1294444800000},"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,4]]},"DOI":"10.1007\/s00453-010-9484-z","type":"journal-article","created":{"date-parts":[[2011,1,7]],"date-time":"2011-01-07T11:30:59Z","timestamp":1294399859000},"page":"807-822","source":"Crossref","is-referenced-by-count":53,"title":["Obtaining a Planar Graph by Vertex Deletion"],"prefix":"10.1007","volume":"62","author":[{"given":"D\u00e1niel","family":"Marx","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ildik\u00f3","family":"Schlotter","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2011,1,8]]},"reference":[{"key":"9484_CR1","first-page":"641","volume-title":"SODA 2008: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"I. Adler","year":"2008","unstructured":"Adler, I., Grohe, M., Kreutzer, S.: Computing excluded minors. In: SODA 2008: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0641\u2013650 (2008)"},{"key":"9484_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/3-540-54487-9_49","volume-title":"CSL 1990: Proceedings of the 4th Workshop on Computer Science Logic","author":"S. Arnborg","year":"1991","unstructured":"Arnborg, S., Proskurowski, A., Seese, D.: Monadic second order logic, tree automata and forbidden minors. In: CSL 1990: Proceedings of the 4th Workshop on Computer Science Logic. Lecture Notes in Computer Science, vol.\u00a0533, pp.\u00a01\u201316. Springer, Berlin (1991)"},{"issue":"1","key":"9484_CR3","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(1), 153\u2013180 (1994)","journal-title":"J. ACM"},{"issue":"1","key":"9484_CR4","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1142\/S0129054194000049","volume":"5","author":"H.L. Bodlaender","year":"1994","unstructured":"Bodlaender, H.L.: On disjoint cycles. Int. J. Found. Comput. Sci. 5(1), 59\u201368 (1994)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"6","key":"9484_CR5","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"9484_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BFb0029946","volume-title":"MFCS 1997: Proceedings of the 22nd International Symposium on Mathematical Foundations of Computer Science","author":"H.L. Bodlaender","year":"1997","unstructured":"Bodlaender, H.L.: Treewidth: Algorithmic techniques and results. In: MFCS 1997: Proceedings of the 22nd International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol.\u00a01295, pp.\u00a019\u201336. Springer, Berlin (1997)"},{"issue":"4","key":"9484_CR7","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","volume":"58","author":"L. Cai","year":"1996","unstructured":"Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett. 58(4), 171\u2013176 (1996)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"9484_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1411509.1411511","volume":"55","author":"J. Chen","year":"2008","unstructured":"Chen, J., Liu, Y., Lu, S., O\u2019Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55(5), 1\u201319 (2008)","journal-title":"J. ACM"},{"key":"9484_CR9","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/B978-0-444-88074-1.50010-X","volume-title":"Handbook of Theoretical Computer Science, Volume\u00a0B: Formal Models and Semantics (B)","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: Graph rewriting: An algebraic and logic approach. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, Volume\u00a0B: Formal Models and Semantics (B), pp.\u00a0193\u2013242. Elsevier\/MIT Press, Amsterdam\/Cambridge (1990)"},{"key":"9484_CR10","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1142\/9789812384720_0005","volume-title":"Handbook of Graph Grammars and Computing by Graph Transformations, Volume\u00a01: Foundations","author":"B. Courcelle","year":"1997","unstructured":"Courcelle, B.: The expression of graph properties and graph transformations in monadic second-order logic. In: Rozenberg, G. (ed.) Handbook of Graph Grammars and Computing by Graph Transformations, Volume\u00a01: Foundations, pp.\u00a0313\u2013400. World Scientific, Singapore (1997)"},{"key":"9484_CR11","first-page":"1194","volume":"3","author":"B. Courcelle","year":"1997","unstructured":"Courcelle, B., Downey, R.G., Fellows, M.R.: A note on the computability of graph minor obstruction sets for monadic second order ideals. J. Univers. Comput. Sci. 3, 1194\u20131198 (1997)","journal-title":"J. Univers. Comput. Sci."},{"key":"9484_CR12","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol.\u00a0173. Springer, Berlin (2005)"},{"key":"9484_CR13","first-page":"161","volume":"87","author":"R.G. Downey","year":"1992","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness. Congr. Numer. 87, 161\u2013187 (1992)","journal-title":"Congr. Numer."},{"key":"9484_CR14","series-title":"Monographs in Computer Science","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. Monographs in Computer Science. Springer, New York (1999)"},{"key":"9484_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2355-7","volume-title":"Mathematical Logic","author":"H.-D. Ebbinghaus","year":"1994","unstructured":"Ebbinghaus, H.-D., Flum, J., Thomas, W.: Mathematical Logic, 2nd\u00a0edn. Springer, Berlin (1994)","edition":"2"},{"issue":"3","key":"9484_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00014","volume":"3","author":"D. Eppstein","year":"1999","unstructured":"Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms Appl. 3(3), 1\u201327 (1999)","journal-title":"J. Graph Algorithms Appl."},{"issue":"3","key":"9484_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(3), 769\u2013779 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"9484_CR18","series-title":"Texts in Theoretical Computer Science. An EATCS Series","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, New York (2006)"},{"issue":"6","key":"9484_CR19","doi-asserted-by":"crossref","first-page":"716","DOI":"10.1145\/602220.602222","volume":"49","author":"J. Flum","year":"2002","unstructured":"Flum, J., Frick, M., Grohe, M.: Query evaluation via tree-decompositions. J. ACM 49(6), 716\u2013752 (2002)","journal-title":"J. ACM"},{"key":"9484_CR20","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1137\/0604033","volume":"4","author":"M.R. Garey","year":"1983","unstructured":"Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM J. Algebr. Discrete Methods 4, 312\u2013316 (1983)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"issue":"2","key":"9484_CR21","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/j.jcss.2003.07.008","volume":"68","author":"M. Grohe","year":"2004","unstructured":"Grohe, M.: Computing crossing numbers in quadratic time. J. Comput. Syst. Sci. 68(2), 285\u2013302 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9484_CR22","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1137\/0204019","volume":"4","author":"F. Hadlock","year":"1975","unstructured":"Hadlock, F.: Finding a maximum cut of a planar graph in polynomial time. SIAM J. Comput. 4(3), 221\u2013225 (1975)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9484_CR23","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J.E. Hopcroft","year":"1974","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Efficient planarity testing. J. ACM 21(4), 549\u2013568 (1974)","journal-title":"J. ACM"},{"key":"9484_CR24","doi-asserted-by":"crossref","first-page":"639","DOI":"10.1109\/FOCS.2009.45","volume-title":"FOCS 2009: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science","author":"K. Kawarabayashi","year":"2009","unstructured":"Kawarabayashi, K.: Planarity allowing few error vertices in linear time. In: FOCS 2009: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pp.\u00a0639\u2013648 (2009)"},{"key":"9484_CR25","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1145\/1250790.1250848","volume-title":"STOC 2007: Proceedings of the 39th Annual ACM Symposium on Theory of Computing","author":"K. Kawarabayashi","year":"2007","unstructured":"Kawarabayashi, K., Reed, B.A.: Computing crossing number in linear time. In: STOC 2007: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp.\u00a0382\u2013390 (2007)"},{"issue":"2","key":"9484_CR26","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"J.M. Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219\u2013230 (1980)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9484_CR27","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(3), 615\u2013627 (1980)","journal-title":"SIAM J. Comput."},{"key":"9484_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/978-3-540-79723-4_14","volume-title":"IWPEC 2008: Proceedings of the Third International Workshop on Parameterized and Exact Computation","author":"D. Lokshtanov","year":"2008","unstructured":"Lokshtanov, D.: Wheel-free deletion is W[2]-hard. In: IWPEC 2008: Proceedings of the Third International Workshop on Parameterized and Exact Computation. Lecture Notes in Computer Science, vol.\u00a05018, pp.\u00a0141\u2013147. Springer, Berlin (2008)"},{"issue":"4","key":"9484_CR29","doi-asserted-by":"crossref","first-page":"747","DOI":"10.1007\/s00453-008-9233-8","volume":"57","author":"D. Marx","year":"2010","unstructured":"Marx, D.: Chordal deletion is fixed-parameter tractable. Algorithmica 57(4), 747\u2013768 (2010)","journal-title":"Algorithmica"},{"key":"9484_CR30","series-title":"Oxford Lecture Series in Mathematics and Its Applications","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications, vol.\u00a031. Oxford University Press, Oxford (2006)"},{"issue":"3","key":"9484_CR31","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1142\/S0129054100000247","volume":"11","author":"L. Perkovic","year":"2000","unstructured":"Perkovic, L., Reed, B.A.: An improved algorithm for finding tree decompositions of small width. Int. J. Found. Comput. Sci. 11(3), 365\u2013371 (2000)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"4","key":"9484_CR32","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"B.A. Reed","year":"2004","unstructured":"Reed, B.A., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32(4), 299\u2013301 (2004)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"9484_CR33","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/0095-8956(86)90030-4","volume":"41","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. V. Excluding a planar graph. J. Comb. Theory, Ser. B 41(1), 92\u2013114 (1986)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"1","key":"9484_CR34","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.D.: 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":"9484_CR35","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"},{"issue":"2","key":"9484_CR36","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.D., 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":"4","key":"9484_CR37","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1016\/0196-6774(89)90006-0","volume":"10","author":"C. Thomassen","year":"1989","unstructured":"Thomassen, C.: The graph genus problem is NP-complete. J. Algorithms 10(4), 568\u2013576 (1989)","journal-title":"J. Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9484-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9484-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9484-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:07Z","timestamp":1559123107000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9484-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1,8]]},"references-count":37,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["9484"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9484-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1,8]]}}}