{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:20Z","timestamp":1740109340745,"version":"3.37.3"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,10,27]],"date-time":"2023-10-27T00:00:00Z","timestamp":1698364800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,27]],"date-time":"2023-10-27T00:00:00Z","timestamp":1698364800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100010607","name":"Universit\u00e0 degli Studi di Perugia","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100010607","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A map is a partition of the sphere into interior-disjoint regions homeomorphic to closed disks. Some regions are labeled as nations, while the remaining ones are labeled as holes. A map in which at most<jats:italic>k<\/jats:italic>nations touch at the same point is a<jats:italic>k<\/jats:italic>-map, while it is hole-free if it contains no holes. A graph is a map graph if there is a bijection between its vertices and the nations of a map, such that two nations touch if and only the corresponding vertices are connected by an edge. We present a fixed-parameter tractable algorithm for recognizing map graphs parameterized by treewidth. Its time complexity is linear in the size of the graph. It reports a certificate in the form of a so-called witness, if the input is a yes-instance. Our algorithmic framework is general enough to test, for any<jats:italic>k<\/jats:italic>, if the input graph admits a<jats:italic>k<\/jats:italic>-map or a hole-free\u00a0<jats:italic>k<\/jats:italic>-map.<\/jats:p>","DOI":"10.1007\/s00453-023-01180-6","type":"journal-article","created":{"date-parts":[[2023,10,27]],"date-time":"2023-10-27T14:02:11Z","timestamp":1698415331000},"page":"613-637","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Recognizing Map Graphs of Bounded Treewidth"],"prefix":"10.1007","volume":"86","author":[{"given":"Patrizio","family":"Angelini","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael A.","family":"Bekos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giordano","family":"Da\u00a0Lozzo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Gronemann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabrizio","family":"Montecchiani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alessandra","family":"Tappini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,10,27]]},"reference":[{"key":"1180_CR1","doi-asserted-by":"crossref","unstructured":"Angelini, P., Bekos, M.A., Da Lozzo, G., Gronemann, M., Montecchiani, F., Tappini, A.: Recognizing map graphs of bounded treewidth. In: SWAT. LIPIcs, vol. 227, pp. 8\u20131818. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, T\u00f3rshavn, Faroe Islands (2022)","DOI":"10.1007\/s00453-023-01180-6"},{"key":"1180_CR2","doi-asserted-by":"crossref","unstructured":"Chen, Z., Grigni, M., Papadimitriou, C.H.: Planar map graphs. In: STOC, pp. 514\u2013523. ACM, Dallas, Texas, USA (1998)","DOI":"10.1145\/276698.276865"},{"issue":"2","key":"1180_CR3","doi-asserted-by":"publisher","first-page":"805","DOI":"10.1137\/16M1062879","volume":"31","author":"V Dujmovic","year":"2017","unstructured":"Dujmovic, V., Eppstein, D., Wood, D.R.: Structure of graphs with locally restricted crossings. SIAM J. Discret. Math. 31(2), 805\u2013824 (2017)","journal-title":"SIAM J. Discret. Math."},{"issue":"4","key":"1180_CR4","doi-asserted-by":"publisher","first-page":"731","DOI":"10.7155\/jgaa.00437","volume":"21","author":"P Angelini","year":"2017","unstructured":"Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M., Rutter, I.: Intersection-link representations of graphs. J. Graph Algorithms Appl. 21(4), 731\u2013755 (2017)","journal-title":"J. Graph Algorithms Appl."},{"key":"1180_CR5","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1016\/j.dam.2019.04.012","volume":"268","author":"FJ Brandenburg","year":"2019","unstructured":"Brandenburg, F.J.: Characterizing 5-map graphs by 2-fan-crossing graphs. Discret. Appl. Math. 268, 10\u201320 (2019)","journal-title":"Discret. Appl. Math."},{"issue":"5","key":"1180_CR6","doi-asserted-by":"publisher","first-page":"1818","DOI":"10.1007\/s00453-018-0510-x","volume":"81","author":"FJ Brandenburg","year":"2019","unstructured":"Brandenburg, F.J.: Characterizing and recognizing 4-map graphs. Algorithmica 81(5), 1818\u20131843 (2019)","journal-title":"Algorithmica"},{"key":"1180_CR7","unstructured":"Chen, Z., He, X., Kao, M.: Nonplanar topological inference and political-map graphs. In: SODA, pp. 195\u2013204. ACM\/SIAM, Baltimore, Maryland, USA (1999)"},{"issue":"1","key":"1180_CR8","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1006\/jagm.2001.1178","volume":"41","author":"Z Chen","year":"2001","unstructured":"Chen, Z.: Approximation algorithms for independent sets in map graphs. J. Algorithms 41(1), 20\u201340 (2001)","journal-title":"J. Algorithms"},{"issue":"1","key":"1180_CR9","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/1077464.1077468","volume":"1","author":"ED Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M.T., Thilikos, D.M.: Fixed-parameter algorithms for ($$k$$, $$r$$)-center in planar graphs and map graphs. ACM Trans. Algorithms 1(1), 33\u201347 (2005)","journal-title":"ACM Trans. Algorithms"},{"key":"1180_CR10","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Misra, N., Saurabh, S.: Planar f-deletion: Approximation, kernelization and optimal FPT algorithms. In: FOCS, pp. 470\u2013479. IEEE, New Brunswick, NJ, USA (2012)","DOI":"10.1109\/FOCS.2012.62"},{"key":"1180_CR11","unstructured":"Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S., Zehavi, M.: Decomposition of map graphs with applications. In: ICALP. LIPIcs, vol. 132, pp. 60\u201316015. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"key":"1180_CR12","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S.: Bidimensionality and geometric graphs. In: SODA, pp. 1563\u20131575. SIAM, Kyoto, Japan (2012)","DOI":"10.1137\/1.9781611973099.124"},{"key":"1180_CR13","doi-asserted-by":"crossref","unstructured":"Chen, Z., Grigni, M., Papadimitriou, C.H.: Map graphs. J. ACM 49(2), 127\u2013138 (2002).","DOI":"10.1145\/506147.506148"},{"key":"1180_CR14","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Map graphs in polynomial time. In: FOCS, pp. 396\u2013405. IEEE, Palo Alto, California, USA (1998)","DOI":"10.1109\/SFCS.1998.743490"},{"issue":"2","key":"1180_CR15","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s00453-005-1184-8","volume":"45","author":"Z Chen","year":"2006","unstructured":"Chen, Z., Grigni, M., Papadimitriou, C.H.: Recognizing hole-free 4-map graphs in cubic time. Algorithmica 45(2), 227\u2013262 (2006)","journal-title":"Algorithmica"},{"key":"1180_CR16","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.disopt.2017.12.002","volume":"28","author":"M Mnich","year":"2018","unstructured":"Mnich, M., Rutter, I., Schmidt, J.M.: Linear-time recognition of map graphs with outerplanar witness. Discret. Optim. 28, 63\u201377 (2018)","journal-title":"Discret. Optim."},{"issue":"4","key":"1180_CR17","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1002\/jgt.20237","volume":"55","author":"Z Chen","year":"2007","unstructured":"Chen, Z.: New bounds on the edge number of a $$k$$-map graph. J. Graph Theory 55(4), 267\u2013290 (2007)","journal-title":"J. Graph Theory"},{"issue":"4","key":"1180_CR18","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/3385731","volume":"67","author":"V Dujmovi\u0107","year":"2020","unstructured":"Dujmovi\u0107, V., Joret, G., Micek, P., Morin, P., Ueckerdt, T., Wood, D.R.: Planar graphs have bounded queue-number. J. ACM 67(4), 22\u201312238 (2020)","journal-title":"J. ACM"},{"key":"1180_CR19","unstructured":"Bekos, M.A., Da Lozzo, G., Hlinen\u00fd, P., Kaufmann, M.: Graph product structure for h-framed graphs. In: ISAAC. LIPIcs, vol. 248, pp. 23\u201312315. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Seoul, Korea (2022)"},{"key":"1180_CR20","unstructured":"Brandenburg, F.J.: Book embeddings of k-map graphs. CoRR abs\/2012.06874 (2020)"},{"key":"1180_CR21","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.tcs.2018.12.010","volume":"772","author":"H Le","year":"2019","unstructured":"Le, H., Le, V.B.: Map graphs having witnesses of large girth. Theor. Comput. Sci. 772, 143\u2013148 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"1180_CR22","unstructured":"Le, H., Le, V.B.: Constrained representations of map graphs and half-squares. In: MFCS. LIPIcs, vol. 138, pp. 13\u201311315. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Aachen, Germany (2019)"},{"issue":"11\u201312","key":"1180_CR23","doi-asserted-by":"publisher","first-page":"4258","DOI":"10.1007\/s00453-018-0440-7","volume":"81","author":"H Le","year":"2019","unstructured":"Le, H., Le, V.B.: Hardness and structural results for half-squares of restricted tree convex bipartite graphs. Algorithmica 81(11\u201312), 4258\u20134274 (2019)","journal-title":"Algorithmica"},{"issue":"3","key":"1180_CR24","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/0206036","volume":"6","author":"S Tsukiyama","year":"1977","unstructured":"Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6(3), 505\u2013517 (1977)","journal-title":"SIAM J. Comput."},{"key":"1180_CR25","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York, USA (1999)"},{"key":"1180_CR26","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986)","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"1180_CR27","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"1180_CR28","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"key":"1180_CR29","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/j.jcss.2021.11.004","volume":"125","author":"E Di Giacomo","year":"2022","unstructured":"Di Giacomo, E., Liotta, G., Montecchiani, F.: Orthogonal planarity testing of bounded treewidth graphs. J. Comput. Syst. Sci. 125, 129\u2013148 (2022)","journal-title":"J. Comput. Syst. Sci."},{"key":"1180_CR30","doi-asserted-by":"crossref","unstructured":"Jansen, B.M.P., Lokshtanov, D., Saurabh, S.: A near-optimal planarization algorithm. In: SODA, pp. 1802\u20131811. SIAM, Oregon, USA (2014)","DOI":"10.1137\/1.9781611973402.130"},{"issue":"9","key":"1180_CR31","doi-asserted-by":"publisher","first-page":"3655","DOI":"10.1007\/s00453-019-00592-7","volume":"81","author":"T Kociumaka","year":"2019","unstructured":"Kociumaka, T., Pilipczuk, M.: Deleting vertices to graphs of bounded genus. Algorithmica 81(9), 3655\u20133691 (2019)","journal-title":"Algorithmica"},{"issue":"6","key":"1180_CR32","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)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1180_CR33","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms 21(2), 358\u2013402 (1996)","journal-title":"J. Algorithms"},{"key":"1180_CR34","doi-asserted-by":"crossref","unstructured":"Kloks, T.: Treewidth, Computations and Approximations. LNCS, vol. 842. Springer, Germany (1994)","DOI":"10.1007\/BFb0045375"},{"issue":"2","key":"1180_CR35","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1145\/3084693.3104030","volume":"15","author":"G Cormode","year":"2017","unstructured":"Cormode, G.: Data sketching. ACM Queue 15(2), 60 (2017)","journal-title":"ACM Queue"},{"key":"1180_CR36","doi-asserted-by":"crossref","unstructured":"Tarjan, R.E., Vishkin, U.: Finding biconnected components and computing tree functions in logarithmic parallel time (extended summary). In: FOCS, pp. 12\u201320. IEEE, West Palm Beach, Florida, USA (1984)","DOI":"10.1109\/SFCS.1984.715896"},{"issue":"1","key":"1180_CR37","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/s00224-008-9150-x","volume":"47","author":"F H\u00fcffner","year":"2010","unstructured":"H\u00fcffner, F., Komusiewicz, C., Moser, H., Niedermeier, R.: Fixed-parameter algorithms for cluster vertex deletion. Theory Comput. Syst. 47(1), 196\u2013217 (2010)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"1180_CR38","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","volume":"46","author":"B Courcelle","year":"1993","unstructured":"Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-rewriting hypergraph grammars. J. Comput. Syst. Sci. 46(2), 218\u2013270 (1993)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01180-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01180-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01180-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,31]],"date-time":"2024-10-31T23:09:29Z","timestamp":1730416169000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01180-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,27]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["1180"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01180-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2023,10,27]]},"assertion":[{"value":"3 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 October 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 October 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}