An algorithmic meta-theorem for graph modification to planarity and FOL

DOI10.1145/3571278MaRDI QIDQ7023431zbMATH OpenFDO

Authors Fedor V. Fomin, Petr A. Golovach, Giannos Stamoulis, Dimitrios M. Thilikos

Publication date 21 February 2025

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3571278

zbMATH Keywords

algorithmic meta-theoremsfirst-order logicgraph modification problemsirrelevant vertex techniqueplanar graphs

Mathematics Subject Classification ID

Logic in computer science (03B70) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A near-optimal planarization algorithm
• Algorithmic meta-theorems
• An algorithm for the graph crossing number problem
• Approximation algorithms for Euler genus and related problems
• Bidimensional Parameters and Local Treewidth
• Can you beat treewidth?
• Contraction obstructions for treewidth
• Deciding first-order properties of locally tree-decomposable structures
• Deciding first-order properties of nowhere dense graphs
• Finding topological subgraphs is fixed-parameter tractable
• Fixed-parameter tractability, definability, and model-checking
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XX: Wagner's conjecture
• Graph structure and monadic second-order logic. A language-theoretic approach
• scientific article; zbMATH DE number 3819693 (Why is no real title available?)
• scientific article; zbMATH DE number 969067 (Why is no real title available?)
• Logic, graphs, and algorithms
• Obtaining a planar graph by vertex deletion
• Obtaining planarity by contracting few edges
• On graph crossing number and edge planarization
• Parametrized complexity theory.
• Planarity Allowing Few Error Vertices in Linear Time
• Testing first-order properties for subclasses of sparse graphs
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The node-deletion problem for hereditary properties is NP-complete
• The parameterized complexity of graph cyclability
• The planar directed k-vertex-disjoint paths problem is fixed-parameter tractable
• Tight bounds for linkages in planar graphs
• Vertex-minors, monadic second-order logic, and a conjecture by Seese

Cited in

(1)

• Advances in algorithmic meta theorems (invited paper)

This page was built for publication: An algorithmic meta-theorem for graph modification to planarity and FOL

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