Angelini, PatrizioBekos, Michael A.Da Lozzo, GiordanoGronemann, MartinMontecchiani, FabrizioTappini, Alessandra2024-09-242024-09-242024Angelini, Patrizio, Michael A. Bekos, Giordano Da Lozzo, Martin Gronemann, Fabrizio Montecchiani, and Alessandra Tappini. “Recognizing Map Graphs of Bounded Treewidth.” Algorithmica 86: 613–637. 2024.https://doi.org/10.1007/s00453-023-01180-6https://hdl.handle.net/20.500.14490/318A 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 k nations touch at the same point is a k-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 k, if the input graph admits a k-map or a hole-free k-map.enAttribution 4.0 Internationalhttp://creativecommons.org/licenses/by/4.0/Map graphsK-map graphsFixed-parameter tractabilityTreewidthArticle