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 metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01370331
Contributor : Dimitrios M. Thilikos <>
Submitted on : Thursday, September 22, 2016 - 1:36:56 PM
Last modification on : Saturday, June 1, 2019 - 11:18:15 AM

File

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

Identifiers

  • HAL Id : lirmm-01370331, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

152

Files downloads

190