Skip to Main content Skip to Navigation
Conference papers

Modification to Planarity is Fixed Parameter Tractable

Abstract : 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.
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download
Contributor : Dimitrios Thilikos Connect in order to contact the contributor
Submitted on : Friday, November 1, 2019 - 12:02:41 PM
Last modification on : Wednesday, November 3, 2021 - 7:44:50 AM
Long-term archiving on: : Sunday, February 2, 2020 - 12:53:08 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License




Fedor V. Fomin, Petr A. Golovach, Dimitrios M. Thilikos. Modification to Planarity is Fixed Parameter Tractable. STACS: Symposium on Theoretical Aspects of Computer Science, Mar 2019, Berlin, Germany. pp.28:1--28:17, ⟨10.4230/LIPIcs.STACS.2019.28⟩. ⟨lirmm-02342768⟩



Record views


Files downloads