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 metadatas

Cited literature [25 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02342768
Contributor : Dimitrios Thilikos <>
Submitted on : Friday, November 1, 2019 - 12:02:41 PM
Last modification on : Tuesday, June 30, 2020 - 3:34:02 PM
Document(s) archivé(s) le : Sunday, February 2, 2020 - 12:53:08 PM

File

LIPIcs-STACS-2019-28.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

38

Files downloads

30