2026-07-24T05:15:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10267 2024-03-06T10:45:40Z ddc:004 open_access

Modification to Planarity is Fixed Parameter Tractable Fomin, Fedor V. Golovach, Petr A. Thilikos, Dimitrios M. Modification problems Planar graphs Irrelevant vertex technique A replacement action is a function L that maps each k-vertex labeled graph to another k-vertex graph. We consider a general family of graph modification problems, called L-Replacement to C, where the input is a graph G and the question is whether it is possible to replace in G some k-vertex subgraph H of it by L(H) so that the new graph belongs to the graph class C. L-Replacement to C can simulate several modification operations such as edge addition, edge removal, edge editing, and diverse completion and superposition operations. In this paper, we prove that for any action L, if C is the class of planar graphs, there is an algorithm that solves L-Replacement to C in O(|G|^{2}) steps. We also present several applications of our approach to related problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fedor V. Fomin and Petr A. Golovach and Dimitrios M. Thilikos 2019 Is Part Of LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2019.28 urn:nbn:de:0030-drops-102677 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.28 eng https://creativecommons.org/licenses/by/3.0/legalcode