{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T13:28:49Z","timestamp":1770902929271,"version":"3.50.1"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032171559","type":"print"},{"value":"9783032171566","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-17156-6_26","type":"book-chapter","created":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T12:36:27Z","timestamp":1770899787000},"page":"351-364","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Outer-Planar Vertex Deletion on\u00a0AT-Free Graphs"],"prefix":"10.1007","author":[{"given":"Joydeep","family":"Mukherjee","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tamojit","family":"Saha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,2,13]]},"reference":[{"key":"26_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/3-540-57155-8_242","volume-title":"Algorithms and Data Structures","author":"H Balakrishnan","year":"1993","unstructured":"Balakrishnan, H., Rajaraman, A., Rangan, C.P.: Connected domination and steiner set on asteroidal triple-free graphs. In: Dehne, F., Sack, J.-R., Santoro, N., Whitesides, S. (eds.) WADS 1993. LNCS, vol. 709, pp. 131\u2013141. Springer, Heidelberg (1993). https:\/\/doi.org\/10.1007\/3-540-57155-8_242"},{"issue":"2","key":"26_CR2","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1137\/S0895480197326346","volume":"12","author":"H Broersma","year":"1999","unstructured":"Broersma, H., Kloks, T., Kratsch, D., M\u00fcller, H.: Independent sets in asteroidal triple-free graphs. SIAM J. Discret. Math. 12(2), 276\u2013287 (1999)","journal-title":"SIAM J. Discret. Math."},{"key":"26_CR3","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.tcs.2018.05.039","volume":"745","author":"Y Cao","year":"2018","unstructured":"Cao, Y., Ke, Y., Otachi, Y., You, J.: Vertex deletion problems on chordal graphs. Theoret. Comput. Sci. 745, 75\u201386 (2018)","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20133","key":"26_CR4","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/S0166-218X(03)00390-1","volume":"132","author":"J-M Chang","year":"2003","unstructured":"Chang, J.-M.: Induced matchings in asteroidal triple-free graphs. Discret. Appl. Math. 132(1\u20133), 67\u201378 (2003)","journal-title":"Discret. Appl. Math."},{"key":"26_CR5","doi-asserted-by":"crossref","unstructured":"Corneil, D.G., Olariu, S., Stewart, L.: Asteroidal triple-free graphs. SIAM J. Discrete Math. 10(3), 399\u2013430 (1997)","DOI":"10.1137\/S0895480193250125"},{"key":"26_CR6","doi-asserted-by":"crossref","unstructured":"Cygan, M., et al.: Parameterized Algorithms, vol.\u00a05. Springer (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"key":"26_CR7","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph theory. Graduate Texts in Mathematics, Springer-Verlag, New York, Incorporateds vol. 173, p. 107 (2000)","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"26_CR8","doi-asserted-by":"crossref","unstructured":"Donkers, H., Jansen, B.M.P., W\u0142odarczyk, M.: Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size. Algorithmica 84(11), 3407\u20133458 (2022)","DOI":"10.1007\/s00453-022-00984-2"},{"issue":"4","key":"26_CR9","doi-asserted-by":"publisher","first-page":"943","DOI":"10.1016\/j.disc.2018.11.023","volume":"342","author":"F Dross","year":"2019","unstructured":"Dross, F., Montassier, M., Pinlou, A.: A lower bound on the order of the largest induced linear forest in triangle-free planar graphs. Discret. Math. 342(4), 943\u2013950 (2019)","journal-title":"Discret. Math."},{"key":"26_CR10","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Misra, N., Philip, G., Saurabh, S.: Hitting forbidden minors: approximation and kernelization. SIAM J. Discrete Math. 30(1), 383\u2013410 (2016)","DOI":"10.1137\/140997889"},{"key":"26_CR11","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Misra, N., Saurabh, S.: Planar F-deletion: approximation, kernelization and optimal FPT algorithms. In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pp. 470\u2013479. IEEE (2012)","DOI":"10.1109\/FOCS.2012.62"},{"key":"26_CR12","doi-asserted-by":"publisher","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Approximation schemes via width\/weight trade-offs on minor-free graphs. In: Chawla, S. (ed.) Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, 5\u20138 January 2020, pp. 2299\u20132318. SIAM (2020). https:\/\/doi.org\/10.1137\/1.9781611975994.141, https:\/\/doi.org\/10.1137\/1.9781611975994.141","DOI":"10.1137\/1.9781611975994.141"},{"key":"26_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/978-3-642-31155-0_14","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"PA Golovach","year":"2012","unstructured":"Golovach, P.A., Paulusma, D., van Leeuwen, E.J.: Induced disjoint paths in AT-free graphs. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol. 7357, pp. 153\u2013164. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31155-0_14"},{"key":"26_CR14","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, vol.\u00a057. Elsevier (2004)","DOI":"10.1016\/S0167-5060(04)80051-7"},{"key":"26_CR15","doi-asserted-by":"crossref","unstructured":"Gupta, A., Lee, E., Li, J., Manurangsi, P., W\u0142odarczyk, M.: Losing treewidth by separating subsets. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 1731\u20131749. SIAM (2019)","DOI":"10.1137\/1.9781611975482.104"},{"key":"26_CR16","doi-asserted-by":"crossref","unstructured":"Jansen, B.M.P., Lokshtanov, D., Saurabh, S.: A near-optimal planarization algorithm. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1802\u20131811. SIAM (2014)","DOI":"10.1137\/1.9781611973402.130"},{"key":"26_CR17","doi-asserted-by":"crossref","unstructured":"Jansen, B.M.P., W\u0142odarczyk, M.: Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 900\u2013913 (2022)","DOI":"10.1145\/3519935.3520021"},{"key":"26_CR18","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K.I.: Planarity allowing few error vertices in linear time. In: 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 639\u2013648. IEEE (2009)","DOI":"10.1109\/FOCS.2009.45"},{"key":"26_CR19","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K.I., Sidiropoulos, A.: Polylogarithmic approximation for minimum planarization (almost). In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 779\u2013788. IEEE (2017)","DOI":"10.1109\/FOCS.2017.77"},{"key":"26_CR20","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K.I., Sidiropoulos, A.: Polylogarithmic approximation for euler genus on bounded degree graphs. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 164\u2013175 (2019)","DOI":"10.1145\/3313276.3316409"},{"key":"26_CR21","doi-asserted-by":"crossref","unstructured":"Klein, C., Strzodka, R.: Highly parallel linear forest extraction from a weighted graph on GPUs. In: Proceedings of the 51st International Conference on Parallel Processing, pp. 1\u201311 (2022)","DOI":"10.1145\/3545008.3545035"},{"issue":"2","key":"26_CR22","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/S0304-3975(96)00206-X","volume":"175","author":"T Kloks","year":"1997","unstructured":"Kloks, T., Kratsch, D., Spinrad, J.: On treewidth and minimum fill-in of asteroidal triple-free graphs. Theoret. Comput. Sci. 175(2), 309\u2013335 (1997)","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20133","key":"26_CR23","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0166-218X(99)00128-6","volume":"99","author":"D Kratsch","year":"2000","unstructured":"Kratsch, D.: Domination and total domination on asteroidal triple-free graphs. Discret. Appl. Math. 99(1\u20133), 111\u2013123 (2000)","journal-title":"Discret. Appl. Math."},{"issue":"10","key":"26_CR24","doi-asserted-by":"publisher","first-page":"1936","DOI":"10.1016\/j.dam.2007.10.006","volume":"156","author":"D Kratsch","year":"2008","unstructured":"Kratsch, D., M\u00fcller, H., Todinca, I.: Feedback vertex set on AT-free graphs. Discret. Appl. Math. 156(10), 1936\u20131947 (2008)","journal-title":"Discret. Appl. Math."},{"key":"26_CR25","doi-asserted-by":"crossref","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)","DOI":"10.1016\/0022-0000(80)90060-4"},{"issue":"3","key":"26_CR26","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), 807\u2013822 (2012)","journal-title":"Algorithmica"},{"key":"26_CR27","unstructured":"Otachi, Y., Suzuki, A., Tamura, Y.: Finding induced subgraphs from graphs with small mim-width. In: 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024), pp. 38\u20131. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2024)"},{"key":"26_CR28","doi-asserted-by":"crossref","unstructured":"Pelsmajer, M.J.: Maximum induced linear forests in outerplanar graphs. Graphs Comb. 20(1), (2004)","DOI":"10.1007\/s00373-003-0528-x"},{"issue":"1","key":"26_CR29","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1002\/jgt.3190140108","volume":"14","author":"KS Poh","year":"1990","unstructured":"Poh, K.S.: On the linear vertex-arboricity of a planar graph. J. Graph Theor. 14(1), 73\u201375 (1990)","journal-title":"J. Graph Theor."},{"issue":"2","key":"26_CR30","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1137\/0210022","volume":"10","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Node-deletion problems on bipartite graphs. SIAM J. Comput. 10(2), 310\u2013327 (1981)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-17156-6_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T12:36:32Z","timestamp":1770899792000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-17156-6_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032171559","9783032171566"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-17156-6_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"13 February 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CALDAM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Algorithms and Discrete Applied Mathematics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Dharwad","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"India","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 February 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 February 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"caldam2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/caldam2026.iitdh.ac.in\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}