Decomposition of map graphs with applications

DOI10.1007/S00454-026-00840-YMaRDI QIDQ7363879zbMATH OpenFDO

Authors Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi

Publication date 1 October 2026

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00454-026-00840-Y

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) General topics in the theory of algorithms (68W01) Analysis of algorithms (68W40)

Cites work

• \textsc{Planar} \(\mathcal{F}\)-\textsc{deletion}: approximation, kernelization and optimal FPT algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Approximation algorithms for independent sets in map graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Bidimensionality: new connections between FPT algorithms and PTASs
• Color-coding
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Efficient computation of representative families with applications in parameterized and exact algorithms
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• Excluded grid minors and efficient polynomial-time approximation schemes
• Faster Algebraic Algorithms for Path and Packing Problems
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Finding, hitting and packing cycles in subexponential time on unit disk graphs
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• scientific article; zbMATH DE number 1775439 (Why is no real title available?)
• scientific article; zbMATH DE number 7053376 (Why is no real title available?)
• Improved bounds on the planar branchwidth with respect to the largest grid minor size
• Kernelization. Theory of parameterized preprocessing
• Map graphs
• Map graphs in polynomial time
• Narrow sieves for parameterized paths and packings
• On problems without polynomial kernels
• Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
• Parameterized algorithms
• Parameterized complexity: exponential speed-up for planar graph problems
• Quickly excluding a planar graph
• Recognizing hole-free 4-map graphs in cubic time
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
• Which problems have strongly exponential complexity?

This page was built for publication: Decomposition of map graphs with applications

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