{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:30:34Z","timestamp":1759638634824},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540748380"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74839-7_28","type":"book-chapter","created":{"date-parts":[[2007,12,6]],"date-time":"2007-12-06T14:55:58Z","timestamp":1196952958000},"page":"292-303","source":"Crossref","is-referenced-by-count":10,"title":["Obtaining a Planar Graph by Vertex Deletion"],"prefix":"10.1007","author":[{"given":"D\u00e1niel","family":"Marx","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ildik\u00f3","family":"Schlotter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"28_CR1","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. J. ACM\u00a041, 153\u2013180 (1994)","journal-title":"J. ACM"},{"key":"28_CR2","doi-asserted-by":"publisher","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.\u00a025, 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"28_CR3","doi-asserted-by":"publisher","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. Inform. Process. Lett.\u00a058, 171\u2013176 (1996)","journal-title":"Inform. Process. Lett."},{"key":"28_CR4","first-page":"194","volume-title":"Handbook of Theoretical Computer Science","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: Graph rewriting: an algebraic and logic approach. In: Handbook of Theoretical Computer Science, vol.\u00a02, pp. 194\u2013242. Elsevier, Amsterdam (1990)"},{"key":"28_CR5","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1142\/9789812384720_0005","volume-title":"Handbook of graph grammars and computing by graph transformations, ch. 5","author":"B. Courcelle","year":"1997","unstructured":"Courcelle, B.: The expression of graph properties and graph transformations in monadic second-order logic. In: Handbook of graph grammars and computing by graph transformations, ch. 5, vol.\u00a01, pp. 313\u2013400. World Scientific, New-Jersey (1997)"},{"key":"28_CR6","volume-title":"Graph Theory","author":"R. Diestel","year":"2000","unstructured":"Diestel, R.: Graph Theory. Springer, Berlin (2000)"},{"key":"28_CR7","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, New York (1999)"},{"key":"28_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1219944.1219946","volume":"3","author":"D. Eppstein","year":"1999","unstructured":"Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms Appl.\u00a03, 1\u201327 (1999)","journal-title":"J. Graph Algorithms Appl."},{"key":"28_CR9","doi-asserted-by":"publisher","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\u00a049, 716\u2013752 (2002)","journal-title":"J. ACM"},{"key":"28_CR10","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. Algebraic Discrete Methods\u00a04, 312\u2013316 (1983)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"28_CR11","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/j.jcss.2003.07.008","volume":"68","author":"M. Grohe","year":"2004","unstructured":"Grohe, M.: Computing crossing number in quadratic time. J. Comput. System Sci.\u00a068, 285\u2013302 (2004)","journal-title":"J. Comput. System Sci."},{"key":"28_CR12","doi-asserted-by":"publisher","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.\u00a04, 221\u2013225 (1975)","journal-title":"SIAM J. Comput."},{"key":"28_CR13","doi-asserted-by":"publisher","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\u00a021, 549\u2013568 (1974)","journal-title":"J. ACM"},{"key":"28_CR14","doi-asserted-by":"publisher","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 vertex-deletion problem for hereditary properties is NP-complete. J. Comput. System Sci.\u00a020, 219\u2013230 (1980)","journal-title":"J. Comput. System Sci."},{"key":"28_CR15","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":"28_CR16","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1142\/S0129054100000247","volume":"11","author":"L. Perkovic","year":"2000","unstructured":"Perkovic, L., Reed, B.: An improved algorithm for finding tree decompositions of small width. Internat. J. Found. Comput. Sci.\u00a011, 365\u2013371 (2000)","journal-title":"Internat. J. Found. Comput. Sci."},{"key":"28_CR17","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.D., Thomas, R.: Quickly excluding a planar graph. J. Combin. Theory Ser. B\u00a062, 323\u2013348 (1994)","journal-title":"J. Combin. Theory Ser. B"},{"key":"28_CR18","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. J. Combin. Theory Ser. B\u00a092, 325\u2013357 (2004)","journal-title":"J. Combin. Theory Ser. B"},{"key":"28_CR19","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.D.: Graph minors. XIII. The disjoint paths problem. J. Combin. Theory Ser. B\u00a063, 65\u2013110 (1995)","journal-title":"J. Combin. Theory Ser. B"},{"key":"28_CR20","doi-asserted-by":"publisher","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\u00a010, 568\u2013576 (1989)","journal-title":"J. Algorithms"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74839-7_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:42:34Z","timestamp":1619520154000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74839-7_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540748380"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74839-7_28","relation":{},"subject":[]}}