FPT Algorithms for Plane Completion Problems - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2016

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))}.
Fichier principal
Vignette du fichier
LIPIcs-MFCS-2016-26.pdf (622.53 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-01370324 , version 1 (22-09-2016)

Licence

Identifiers

Cite

Dimitris Chatzidimitriou, Archontia C. 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⟩
182 View
162 Download

Altmetric

Share

More