{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T20:57:02Z","timestamp":1775595422231,"version":"3.50.1"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T00:00:00Z","timestamp":1559865600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T00:00:00Z","timestamp":1559865600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["DEC- 2012\/05\/D\/ST6\/03214"],"award-info":[{"award-number":["DEC- 2012\/05\/D\/ST6\/03214"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,9]]},"DOI":"10.1007\/s00453-019-00592-7","type":"journal-article","created":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T05:02:38Z","timestamp":1559883758000},"page":"3655-3691","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Deleting Vertices to Graphs of Bounded Genus"],"prefix":"10.1007","volume":"81","author":[{"given":"Tomasz","family":"Kociumaka","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5680-7397","authenticated-orcid":false,"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,6,7]]},"reference":[{"issue":"6","key":"592_CR1","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL 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). \n                    https:\/\/doi.org\/10.1137\/S0097539793251219","journal-title":"SIAM J. Comput."},{"key":"592_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015). \n                    https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"592_CR3","doi-asserted-by":"publisher","unstructured":"Demaine, E.D., Hajiaghayi, M.T., Kawarabayashi, K.: Algorithmic graph minor theory: decomposition, approximation, and coloring. In: 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005, pp. 637\u2013646. IEEE Computer Society (2005). \n                    https:\/\/doi.org\/10.1109\/SFCS.2005.14","DOI":"10.1109\/SFCS.2005.14"},{"issue":"1","key":"592_CR4","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/s00493-008-2140-4","volume":"28","author":"ED Demaine","year":"2008","unstructured":"Demaine, E.D., Hajiaghayi, M.: Linearity of grid minors in treewidth with applications through bidimensionality. Combinatorica 28(1), 19\u201336 (2008). \n                    https:\/\/doi.org\/10.1007\/s00493-008-2140-4","journal-title":"Combinatorica"},{"key":"592_CR5","doi-asserted-by":"publisher","unstructured":"Diestel, R.: Graph Theory, volume 173 of Graduate Texts in Mathematics, 5th edn. Springer, Heidelberg (2017). \n                    https:\/\/doi.org\/10.1007\/978-3-662-53622-3","DOI":"10.1007\/978-3-662-53622-3"},{"issue":"4","key":"592_CR6","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001). \n                    https:\/\/doi.org\/10.1006\/jcss.2001.1774","journal-title":"J. Comput. Syst. Sci."},{"key":"592_CR7","doi-asserted-by":"publisher","unstructured":"Jansen, B.M.P., Lokshtanov, D., Saurabh, S.: A near-optimal planarization algorithm. In: Chekuri, C. (ed.) 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pp. 1802\u20131811. SIAM (2014). \n                    https:\/\/doi.org\/10.1137\/1.9781611973402.130","DOI":"10.1137\/1.9781611973402.130"},{"key":"592_CR8","doi-asserted-by":"publisher","unstructured":"Kawarabayashi, K.: Planarity allowing few error vertices in linear time. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, pp. 639\u2013648. IEEE Computer Society (2009). \n                    https:\/\/doi.org\/10.1109\/FOCS.2009.45","DOI":"10.1109\/FOCS.2009.45"},{"key":"592_CR9","doi-asserted-by":"publisher","unstructured":"Kawarabayashi, K., Mohar, B., Reed, B.A.: A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width. In: 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, pp. 771\u2013780. IEEE Computer Society (2008). \n                    https:\/\/doi.org\/10.1109\/FOCS.2008.53","DOI":"10.1109\/FOCS.2008.53"},{"key":"592_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth, Computations and Approximations, volume 842 of LNCS","author":"T Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth, Computations and Approximations, volume 842 of LNCS. Springer, Berlin (1994). \n                    https:\/\/doi.org\/10.1007\/BFb0045375"},{"issue":"2","key":"592_CR11","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"JM 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). \n                    https:\/\/doi.org\/10.1016\/0022-0000(80)90060-4","journal-title":"J. Comput. Syst. Sci."},{"issue":"3\u20134","key":"592_CR12","doi-asserted-by":"publisher","first-page":"807","DOI":"10.1007\/s00453-010-9484-z","volume":"62","author":"D Marx","year":"2012","unstructured":"Marx, D., Schlotter, I.: Obtaining a planar graph by vertex deletion. Algorithmica 62(3\u20134), 807\u2013822 (2012). \n                    https:\/\/doi.org\/10.1007\/s00453-010-9484-z","journal-title":"Algorithmica"},{"issue":"1","key":"592_CR13","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1137\/S089548019529248X","volume":"12","author":"B Mohar","year":"1999","unstructured":"Mohar, B.: A linear time algorithm for embedding graphs in an arbitrary surface. SIAM J. Discrete Math. 12(1), 6\u201326 (1999). \n                    https:\/\/doi.org\/10.1137\/S089548019529248X","journal-title":"SIAM J. Discrete Math."},{"key":"592_CR14","unstructured":"Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press (2001). \n                    https:\/\/jhupbooks.press.jhu.edu\/title\/graphs-surfaces\n                    \n                  . Accessed 03 June 2019"},{"key":"592_CR15","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.dam.2016.05.019","volume":"231","author":"M Pilipczuk","year":"2017","unstructured":"Pilipczuk, M.: A tight lower bound for vertex planarization on graphs of bounded treewidth. Discrete Appl. Math. 231, 211\u2013216 (2017). \n                    https:\/\/doi.org\/10.1016\/j.dam.2016.05.019","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"592_CR16","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1002\/jgt.3190010114","volume":"1","author":"S Stahl","year":"1977","unstructured":"Stahl, S., Beineke, L.W.: Blocks and the nonorientable genus of graphs. J. Graph Theory 1(1), 75\u201378 (1977). \n                    https:\/\/doi.org\/10.1002\/jgt.3190010114","journal-title":"J. Graph Theory"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00592-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00592-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00592-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,5]],"date-time":"2020-06-05T23:28:18Z","timestamp":1591399698000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00592-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,7]]},"references-count":16,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["592"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00592-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,7]]},"assertion":[{"value":"13 June 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 May 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}