License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2022.8
URN: urn:nbn:de:0030-drops-161681
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16168/
Go to the corresponding LIPIcs Volume Portal

Angelini, Patrizio ; Bekos, Michael A. ; Da Lozzo, Giordano ; Gronemann, Martin ; Montecchiani, Fabrizio ; Tappini, Alessandra

Recognizing Map Graphs of Bounded Treewidth

pdf-format:
LIPIcs-SWAT-2022-8.pdf (1 MB)

Abstract

A map graph is one admitting a representation in which vertices are nations on a spherical map and edges are shared curve segments or points between nations. We present an explicit fixed-parameter tractable algorithm for recognizing map graphs parameterized by treewidth. The algorithm has time complexity that is linear in the size of the graph and, if the input is a yes-instance, it reports a certificate in the form of a so-called witness. Furthermore, this result is developed within a more general algorithmic framework that allows to test, for any k, if the input graph admits a k-map (where at most k nations meet at a common point) or a hole-free k-map (where each point is covered by at least one nation). We point out that, although bounding the treewidth of the input graph also bounds the size of its largest clique, the latter alone does not seem to be a strong enough structural limitation to obtain an efficient time complexity. In fact, while the largest clique in a k-map graph is ⌊ 3k/2 ⌋, the recognition of k-map graphs is still open for any fixed k ≥ 5.

BibTeX - Entry

@InProceedings{angelini_et_al:LIPIcs.SWAT.2022.8,
  author =	{Angelini, Patrizio and Bekos, Michael A. and Da Lozzo, Giordano and Gronemann, Martin and Montecchiani, Fabrizio and Tappini, Alessandra},
  title =	{{Recognizing Map Graphs of Bounded Treewidth}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16168},
  URN =		{urn:nbn:de:0030-drops-161681},
  doi =		{10.4230/LIPIcs.SWAT.2022.8},
  annote =	{Keywords: Map graphs, Recognition, Parameterized complexity}
}

Keywords: Map graphs, Recognition, Parameterized complexity
Collection: 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Issue Date: 2022
Date of publication: 22.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI