Conference Papers Year : 2015

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.
Fichier principal
Vignette du fichier
ctw2015_template_psc camera ready.pdf (310.16 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-01370331 , version 1 (22-09-2016)

Identifiers

  • HAL Id : lirmm-01370331 , version 1

Cite

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⟩
144 View
136 Download

Share

More