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))}.
Type de document :
Communication dans un congrès
MFCS: Mathematical Foundations of Computer Science, Aug 2016, Kraków, Poland. 41st International Symposium on Mathematical Foundations of Computer Science, 58, pp.26:1-26:13, 2016, Leibniz International Proceedings in Informatics (LIPIcs). 〈10.4230/LIPIcs.MFCS.2016.26〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01370324
Contributeur : Dimitrios M. Thilikos <>
Soumis le : jeudi 22 septembre 2016 - 13:21:12
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Fichier

LIPIcs-MFCS-2016-26.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

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. 41st International Symposium on Mathematical Foundations of Computer Science, 58, pp.26:1-26:13, 2016, Leibniz International Proceedings in Informatics (LIPIcs). 〈10.4230/LIPIcs.MFCS.2016.26〉. 〈lirmm-01370324〉

Partager

Métriques

Consultations de la notice

81

Téléchargements de fichiers

97