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))}.
Domains
Discrete Mathematics [cs.DM]Origin | Files produced by the author(s) |
---|