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

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In general, a graph modification problem is defined by a graph modification operation and a target graph property P. Typically, the modification operation may be vertex removal, edge removal, edge contraction, or edge addition and the question is, given a graph G and an integer k, whether it is possible to transform G to a graph in P after applying k times the operation on G. This problem has been extensively studied for particilar instantiations of and P. In this paper we consider the general property Pφ of being planar and, moreover, being a model of some First-Order Logic sentence φ (an FOL-sentence). We call the corresponding meta-problem Graph -Modification to Planarity and φ and prove the following algorithmic meta-theorem: there exists a function f : N2 → N such that, for every and every FOL sentence φ, the Graph Modification to Planarity and φ is solvable in f(k, |φ|) · n2 time. The proof constitutes a hybrid of two different classic techniques in graph algorithms. The first is the irrelevant vertex technique that is typically used in the context of Graph Minors and deals with properties such as planarity or surface-embeddability (that are not FOL-expressible) and the second is the use of Gaifman’s Locality Theorem that is the theoretical base for the meta-algorithmic study of FOL-expressible problems.

Original languageEnglish (US)
Title of host publication28th Annual European Symposium on Algorithms, ESA 2020
EditorsFabrizio Grandoni, Grzegorz Herman, Peter Sanders
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771627
StatePublished - Aug 1 2020
Event28th Annual European Symposium on Algorithms, ESA 2020 - Virtual, Pisa, Italy
Duration: Sep 7 2020Sep 9 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference28th Annual European Symposium on Algorithms, ESA 2020
CityVirtual, Pisa


  • Algorithmic meta-theorems
  • First Order Logic
  • Graph modification Problems
  • Irrelevant vertex technique
  • Planar graphs
  • Surface embeddable graphs

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'An algorithmic meta-theorem for graph modification to planarity and FOL'. Together they form a unique fingerprint.

Cite this