{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:32:07Z","timestamp":1771036327694,"version":"3.50.1"},"publisher-location":"Cham","reference-count":16,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031754081","type":"print"},{"value":"9783031754098","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-3-031-75409-8_8","type":"book-chapter","created":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T22:10:36Z","timestamp":1737497436000},"page":"107-120","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["XNLP-Hardness of\u00a0Parameterized Problems on\u00a0Planar Graphs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9297-3330","authenticated-orcid":false,"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3570-0528","authenticated-orcid":false,"given":"Krisztina","family":"Szil\u00e1gyi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,22]]},"reference":[{"issue":"3","key":"8_CR1","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1145\/990308.990309","volume":"51","author":"J Alber","year":"2004","unstructured":"Alber, J., Fellows, M.R., Niedermeier, R.: Polynomial-time data reduction for dominating set. J. ACM 51(3), 363\u2013384 (2004). https:\/\/doi.org\/10.1145\/990308.990309","journal-title":"J. ACM"},{"key":"8_CR2","unstructured":"Alexandersson, P.: NP-complete variants of some classical graph problems. arXiv, abs\/2001.04120 (2020). http:\/\/arxiv.org\/abs\/2001.04120"},{"issue":"1","key":"8_CR3","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153\u2013180 (1994). https:\/\/doi.org\/10.1145\/174644.174650","journal-title":"J. ACM"},{"issue":"1\u20132","key":"8_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial $$k$$-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. 209(1\u20132), 1\u201345 (1998). https:\/\/doi.org\/10.1016\/S0304-3975(97)00228-4","journal-title":"Theoret. Comput. Sci."},{"key":"8_CR5","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Cornelissen, G., van\u00a0der Wegen, M.: Problems hard for treewidth but easy for stable gonality. In: Bekos, M.A., Kaufmann, M. (eds.) Proceedings 48th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2022, volume 13453 of Lecture Notes in Computer Science, pp. 84\u201397. Springer (2022). https:\/\/doi.org\/10.1007\/978-3-031-15914-5_7","DOI":"10.1007\/978-3-031-15914-5_7"},{"key":"8_CR6","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Groenland, C., Jacob, H., Jaffke, L., Lima, P.T.: XNLP-completeness for parameterized problems on graphs with a linear structure. In: Dell, H., Nederlof, J. (eds.)Proceedings 17th International Symposium on Parameterized and Exact Computation, IPEC 2022, volume 249 of LIPIcs, pp. 8:1\u20138:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2022.8","DOI":"10.4230\/LIPIcs.IPEC.2022.8"},{"key":"8_CR7","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Groenland, C., Jacob, H., Pilipczuk, M., Pilipczuk, M.: On the complexity of problems on tree-structured graphs. In: Dell, H., Nederlof, J., (eds.) Proceedings 17th International Symposium on Parameterized and Exact Computation, IPEC 2022, volume 249 of LIPIcs, pp. 6:1\u20136:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2022.6","DOI":"10.4230\/LIPIcs.IPEC.2022.6"},{"key":"8_CR8","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Groenland, C., Nederlof, J., Swennenhuis, C.M.F.: Parameterized problems complete for nondeterministic FPT time and logarithmic space. In: Proceedings 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, pp. 193\u2013204. IEEE (2022). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00027","DOI":"10.1109\/FOCS52979.2021.00027"},{"key":"8_CR9","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Mannens, I., Oostveen, J.J., Pandey, S., van Leeuwen, E.J.: The parameterised complexity of integer multicommodity flow. In: Misra, N., Wahlstr\u00f6m, M. (eds.)Proceedings 18th International Symposium on Parameterized and Exact Computation, IPEC 2023, volume 285 of LIPIcs, pp. 6:1\u20136:19. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023). https:\/\/doi.org\/10.4230\/LIPICS.IPEC.2023.6","DOI":"10.4230\/LIPICS.IPEC.2023.6"},{"key":"8_CR10","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Szil\u00e1gyi, K.: XNLP-hardness of parameterized problems on planar graphs. arXiv, abs\/1004.2642 (2024). https:\/\/doi.org\/10.48550\/arXiv.2402.03087","DOI":"10.48550\/arXiv.2402.03087"},{"issue":"4","key":"8_CR11","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness I: basic results. SIAM J. Comput. 24(4), 873\u2013921 (1995). https:\/\/doi.org\/10.1137\/S0097539792228228","journal-title":"SIAM J. Comput."},{"issue":"3","key":"8_CR12","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1007\/s00453-014-9944-y","volume":"71","author":"M Elberfeld","year":"2014","unstructured":"Elberfeld, M., Stockhusen, C., Tantau, T.: On the space and circuit complexity of parameterized problems: classes and completeness. Algorithmica 71(3), 661\u2013701 (2014). https:\/\/doi.org\/10.1007\/s00453-014-9944-y","journal-title":"Algorithmica"},{"key":"8_CR13","doi-asserted-by":"publisher","unstructured":"Erd\u00f6s, P., Tur\u00e1n, P.: On a problem of Sidon in additive number theory, and on some related problems. J. London Math. Soc. s1-16(4), 212\u2013215 (1941). https:\/\/doi.org\/10.1112\/jlms\/s1-16.4.212","DOI":"10.1112\/jlms\/s1-16.4.212"},{"key":"8_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/978-3-540-75520-3_33","volume-title":"Algorithms \u2013 ESA 2007","author":"F Kammer","year":"2007","unstructured":"Kammer, F.: Determining the smallest k Such That G Is k-Outerplanar. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol. 4698, pp. 359\u2013370. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-75520-3_33"},{"key":"8_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/BFB0045375","author":"T Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth, Computations and Approximations, volume 842 of Lecture Notes in Computer Science. Springer (1994). https:\/\/doi.org\/10.1007\/BFB0045375","journal-title":"Springer"},{"key":"8_CR16","doi-asserted-by":"publisher","unstructured":"Pilipczuk, M., Wrochna, M.: On space efficiency of algorithms working on structural decompositions of graphs. ACM Trans. Comput. Theo. 9(4), 18:1\u201318:36 (2018). https:\/\/doi.org\/10.1145\/3154856","DOI":"10.1145\/3154856"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-75409-8_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T22:10:38Z","timestamp":1737497438000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-75409-8_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031754081","9783031754098"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-75409-8_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"22 January 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Gozd Martuljek","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Slovenia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 June 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"50","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/conferences.famnit.upr.si\/event\/31\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}