Loading...
Recognizing Map Graphs of Bounded Treewidth
Angelini, Patrizio
Bekos, Michael A. Da Lozzo, Giordano Gronemann, Martin Montecchiani, Fabrizio Tappini, Alessandra
Bekos, Michael A.
Da Lozzo, Giordano
Gronemann, Martin
Montecchiani, Fabrizio
Tappini, Alessandra
Citations
Altmetric:
Abstract
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 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.
Description
Date
2024
Journal Title
Journal ISSN
Volume Title
Publisher
Springer Nature
Research Projects
Organizational Units
Journal Issue
Keywords
Map graphs, K-map graphs, Fixed-parameter tractability, Treewidth
Citation
Angelini, 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.