FPT Algorithms for Plane Completion Problems

Abstract : The Plane Subgraph (resp. Topological Minor) Completion problem asks, given a (possibly disconnected) plane (multi)graph Γ and a connected plane (multi)graph ∆, whether it is possible to add edges in Γ without violating the planarity of its embedding so that it contains some subgraph (resp. topological minor) that is topologically isomorphic to ∆. We give FPT algorithms that solve both problems in f (|E(∆)|) · |E(Γ)| 2 steps. Moreover, for the Plane Subgraph Completion problem we show that f(k)=2^{O(k*log(k))}.
Document type :
Conference papers
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01370324
Contributor : Dimitrios M. Thilikos <>
Submitted on : Thursday, September 22, 2016 - 1:21:12 PM
Last modification on : Thursday, June 20, 2019 - 1:26:51 PM

File

LIPIcs-MFCS-2016-26.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Collections

Citation

Dimitris Chatzidimitriou, Archontia Giannopoulou, Spyridon Maniatis, Clément Requilé, Dimitrios M. Thilikos, et al.. FPT Algorithms for Plane Completion Problems. MFCS: Mathematical Foundations of Computer Science, Aug 2016, Kraków, Poland. pp.26:1-26:13, ⟨10.4230/LIPIcs.MFCS.2016.26⟩. ⟨lirmm-01370324⟩

Share

Metrics

Record views

190

Files downloads

209