{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:47:00Z","timestamp":1742914020511,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031754081"},{"type":"electronic","value":"9783031754098"}],"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_30","type":"book-chapter","created":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T22:10:41Z","timestamp":1737497441000},"page":"430-443","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Exact and\u00a0Approximate k-planarity Testing for\u00a0Maximal Graphs of\u00a0Small Pathwidth"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6997-8774","authenticated-orcid":false,"given":"Miriam","family":"M\u00fcnch","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7203-0669","authenticated-orcid":false,"given":"Maximilian","family":"Pfister","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3794-4406","authenticated-orcid":false,"given":"Ignaz","family":"Rutter","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,22]]},"reference":[{"key":"30_CR1","doi-asserted-by":"publisher","unstructured":"Ackerman, E.: On topological graphs with at most four crossings per edge. Comput. Geom. 85 (2019). https:\/\/doi.org\/10.1016\/j.comgeo.2019.101574","DOI":"10.1016\/j.comgeo.2019.101574"},{"issue":"4","key":"30_CR2","doi-asserted-by":"publisher","first-page":"573","DOI":"10.7155\/jgaa.00531","volume":"24","author":"P Angelini","year":"2020","unstructured":"Angelini, P., Bekos, M.A., Kaufmann, M., Schneck, T.: Efficient generation of different topological representations of graphs beyond-planarity. J. Graph Algorithms Appl. 24(4), 573\u2013601 (2020). https:\/\/doi.org\/10.7155\/jgaa.00531","journal-title":"J. Graph Algorithms Appl."},{"issue":"1","key":"30_CR3","doi-asserted-by":"publisher","first-page":"23","DOI":"10.7155\/jgaa.00457","volume":"22","author":"MJ Bannister","year":"2018","unstructured":"Bannister, M.J., Cabello, S., Eppstein, D.: Parameterized complexity of 1-planarity. J. Graph Algorithms Appl. 22(1), 23\u201349 (2018). https:\/\/doi.org\/10.7155\/jgaa.00457","journal-title":"J. Graph Algorithms Appl."},{"key":"30_CR4","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1002\/mana.3211170125","volume":"117","author":"R Bodendiek","year":"1984","unstructured":"Bodendiek, R., Schumacher, H., Wagner, K.: \u00dcber 1-optimale Graphen. Math. Nachr. 117, 323\u2013339 (1984)","journal-title":"Math. Nachr."},{"issue":"3","key":"30_CR5","doi-asserted-by":"publisher","first-page":"241","DOI":"10.7155\/jgaa.00091","volume":"8","author":"JM Boyer","year":"2004","unstructured":"Boyer, J.M., Myrvold, W.J.: On the cutting edge: simplified O(n) planarity by edge addition. J. Graph Algorithms Appl. 8(3), 241\u2013273 (2004). https:\/\/doi.org\/10.7155\/jgaa.00091","journal-title":"J. Graph Algorithms Appl."},{"issue":"4\u20135","key":"30_CR6","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1016\/j.dam.2011.11.014","volume":"160","author":"J Czap","year":"2012","unstructured":"Czap, J., Hud\u00e1k, D.: 1-planarity of complete multipartite graphs. Discret. Appl. Math. 160(4\u20135), 505\u2013512 (2012). https:\/\/doi.org\/10.1016\/j.dam.2011.11.014","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"30_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-007-0010-x","volume":"49","author":"A Grigoriev","year":"2007","unstructured":"Grigoriev, A., Bodlaender, H.L.: Algorithms for graphs embeddable with few crossings per edge. Algorithmica 49(1), 1\u201311 (2007). https:\/\/doi.org\/10.1007\/s00453-007-0010-x","journal-title":"Algorithmica"},{"key":"30_CR8","doi-asserted-by":"publisher","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Efficient planarity testing. J. ACM 21(4) (1974). https:\/\/doi.org\/10.1145\/321850.321852","DOI":"10.1145\/321850.321852"},{"key":"30_CR9","doi-asserted-by":"crossref","unstructured":"Korzhik, V.P.: Minimal non-1-planar graphs. Discrete Math. 308(7), 1319\u20131327 (2008). https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0012365X07002087","DOI":"10.1016\/j.disc.2007.04.009"},{"issue":"1","key":"30_CR10","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1002\/jgt.21630","volume":"72","author":"VP Korzhik","year":"2013","unstructured":"Korzhik, V.P., Mohar, B.: Minimal obstructions for 1-immersions and hardness of 1-planarity testing. J. Graph Theory 72(1), 30\u201371 (2013). https:\/\/doi.org\/10.1002\/jgt.21630","journal-title":"J. Graph Theory"},{"key":"30_CR11","doi-asserted-by":"publisher","first-page":"217","DOI":"10.4064\/fm-15-1-271-283","volume":"15","author":"K Kuratowski","year":"1930","unstructured":"Kuratowski, K.: Sur le probl\u00e8me des courbes gauches en topologie. Fund. Math. 15, 217\u2013283 (1930)","journal-title":"Fund. Math."},{"key":"30_CR12","doi-asserted-by":"crossref","unstructured":"Mutzel, P.: An alternative method to crossing minimization on hierarchical graphs. In: GD. Lecture Notes in Computer Science, vol. 1190, pp. 318\u2013333. Springer (1996)","DOI":"10.1007\/3-540-62495-3_57"},{"issue":"1","key":"30_CR13","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1002\/(SICI)1097-0118(199601)21:1<51::AID-JGT7>3.0.CO;2-L","volume":"21","author":"RB Richter","year":"1996","unstructured":"Richter, R.B., \u0160ir\u00e1\u0148, J.: The crossing number of $${K}_{3, n}$$ in a surface. J. Graph Theory 21(1), 51\u201354 (1996)","journal-title":"J. Graph Theory"},{"key":"30_CR14","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/BF02996313","volume":"29","author":"G Ringel","year":"1965","unstructured":"Ringel, G.: Ein Sechsfarbenproblem auf der Kugel. Abh. Math. Sem. Univ. Hamb. 29, 107\u2013117 (1965)","journal-title":"Abh. Math. Sem. Univ. Hamb."},{"key":"30_CR15","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner\u2019s conjecture. J. Comb. Theory, Ser. B 92, 325\u2013357 (2004)","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"30_CR16","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-981-15-6533-5_4","volume-title":"Beyond Planar Graphs","author":"Y Suzuki","year":"2020","unstructured":"Suzuki, Y.: 1-Planar graphs. In: Hong, S.-H., Tokuyama, T. (eds.) Beyond Planar Graphs, pp. 47\u201368. Springer, Singapore (2020). https:\/\/doi.org\/10.1007\/978-981-15-6533-5_4"},{"issue":"2","key":"30_CR17","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/s00453-019-00653-x","volume":"82","author":"T Biedl","year":"2020","unstructured":"Biedl, T., Chimani, M., Derka, M., Mutzel, P.: Crossing number for graphs with bounded pathwidth. Algorithmica 82(2), 355\u2013384 (2020). https:\/\/doi.org\/10.1007\/s00453-019-00653-x","journal-title":"Algorithmica"},{"key":"30_CR18","doi-asserted-by":"publisher","first-page":"106083","DOI":"10.1016\/j.ipl.2020.106083","volume":"169","author":"JC Urschel","year":"2021","unstructured":"Urschel, J.C., Wellens, J.: Testing gap k-planarity is NP-complete. Inf. Process. Lett. 169, 106083 (2021). https:\/\/doi.org\/10.1016\/j.ipl.2020.106083","journal-title":"Inf. Process. Lett."},{"key":"30_CR19","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1007\/BF01594196","volume":"114","author":"K Wagner","year":"1937","unstructured":"Wagner, K.: \u00dcber eine Eigenschaft der ebenen Komplexe. Math. Ann. 114, 570\u2013590 (1937)","journal-title":"Math. Ann."}],"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_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T22:10:43Z","timestamp":1737497443000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-75409-8_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031754081","9783031754098"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-75409-8_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"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"}}]}}