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.
Type de document :
Communication dans un congrès
CTW: Cologne-Twente Workshop on Graphs & Combinatorial Optimization, May 2015, Istanbul, Turkey. 13th Cologne-Twente Workshop on Graphs & Combinatorial Optimization, 2015, 〈http://ctw2015.eng.marmara.edu.tr〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01370331
Contributeur : Dimitrios M. Thilikos <>
Soumis le : jeudi 22 septembre 2016 - 13:36:56
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Fichier

ctw2015_template_psc camera re...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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 & Combinatorial Optimization, May 2015, Istanbul, Turkey. 13th Cologne-Twente Workshop on Graphs & Combinatorial Optimization, 2015, 〈http://ctw2015.eng.marmara.edu.tr〉. 〈lirmm-01370331〉

Partager

Métriques

Consultations de la notice

100

Téléchargements de fichiers

89