Skip to Main content Skip to Navigation
Conference papers

A Fixed Parameter Algorithm for Plane Subgraph Completion

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Dimitrios Thilikos Connect in order to contact the contributor
Submitted on : Thursday, September 22, 2016 - 1:36:56 PM
Last modification on : Monday, October 11, 2021 - 1:24:08 PM


ctw2015_template_psc camera re...
Files produced by the author(s)


  • HAL Id : lirmm-01370331, version 1



Dimitris Chatzidimitriou, Archontia C. Giannopoulou, Clément Requilé, Dimitrios M. Thilikos, Dimitris Zoros. A Fixed Parameter Algorithm for Plane Subgraph Completion. CTW: Cologne-Twente Workshop on Graphs and Combinatorial Optimization, May 2015, Istanbul, Turkey. ⟨lirmm-01370331⟩



Record views


Files downloads