2026-07-21T19:24:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6441 2024-03-06T10:38:17Z ddc:004 open_access

FPT Algorithms for Plane Completion Problems Chatzidimitriou, Dimitris Giannopoulou, Archontia C. Maniatis, Spyridon Requilé, Clément Thilikos, Dimitrios M. Zoros, Dimitris completion problems FPT plane graphs topological isomorphism The Plane Subgraph (resp. Topological Minor) Completion problem asks, given a (possibly disconnected) plane (multi)graph Gamma and a connected plane (multi)graph Delta, whether it is possible to add edges in Gamma without violating the planarity of its embedding so that it contains some subgraph (resp. topological minor) that is topologically isomorphic to Delta. We give FPT algorithms that solve both problems in f(|E(Delta)|)*|E(\Gamma)|^{2} steps. Moreover, for the Plane Subgraph Completion problem we show that f(k)=2^{O(k*log(k))}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dimitris Chatzidimitriou and Archontia C. Giannopoulou and Spyridon Maniatis and Clément Requilé and Dimitrios M. Thilikos and Dimitris Zoros 2016 Is Part Of LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2016.26 urn:nbn:de:0030-drops-64418 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.26 eng https://creativecommons.org/licenses/by/3.0/legalcode