Modification to planarity is fixed parameter tractable
Peer reviewed, Journal article
Published version
View/ Open
Date
2019Metadata
Show full item recordCollections
Original version
https://doi.org/10.4230/lipics.stacs.2019.28Abstract
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.