Recognizing map graphs of bounded treewidth

DOI10.1007/S00453-023-01180-6MaRDI QIDQ6182682zbMATH OpenOpenAlexFDO

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

Publication date 25 January 2024

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2206.14898

zbMATH Keywords

fixed-parameter tractabilityK-map graphsmap graphstreewidth

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

Abstract: A map graph is a graph 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 of the sphere 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 $lfloor3k/2floor$, the recognition of $k$-map graphs is still open for any fixed $kge5$.

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A near-optimal planarization algorithm
• A New Algorithm for Generating All the Maximal Independent Sets
• Approximation algorithms for independent sets in map graphs
• Characterizing 5-map graphs by 2-fan-crossing graphs
• Characterizing and recognizing 4-map graphs
• Constrained representations of map graphs and half-squares
• Decomposition of Map Graphs with Applications.
• Deleting vertices to graphs of bounded genus
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Fixed-parameter algorithms for cluster vertex deletion
• Graph minors. II. Algorithmic aspects of tree-width
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 1305408 (Why is no real title available?)
• scientific article; zbMATH DE number 1775439 (Why is no real title available?)
• scientific article; zbMATH DE number 7053376 (Why is no real title available?)
• Intersection-link representations of graphs
• Linear-time recognition of map graphs with outerplanar witness
• Map graphs
• Map graphs having witnesses of large girth
• New bounds on the edge number of ak-map graph
• Orthogonal planarity testing of bounded treewidth graphs
• Parameterized algorithms
• Planar graphs have bounded queue-number
• Recognizing hole-free 4-map graphs in cubic time
• Structure of graphs with locally restricted crossings
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Treewidth. Computations and approximations

This page was built for publication: Recognizing map graphs of bounded treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6182682)