A Fixed Parameter Algorithm for Plane Subgraph Completion

International audience; The Plane Subgraph Completion problem asks, given a (possibly disconnected) plane graph Γ and a connected plane graph ∆, whether it is possible to add edges in Γ such that the resulting graph remains planar and contains some subgraph that is topologically isomorphic to ∆. We give an algorithm that solves this problem in 2 O(k log k) · n 2 steps where k and n are the number of vertices of ∆ and Γ respectively.