# Variants of Plane Diameter Completion

2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The {\sc Plane Diameter Completion} problem asks, given a plane graph $G$ and a positive integer $d$, if it is a spanning subgraph of a plane graph $H$ that has diameter at most $d$. We examine two variants of this problem where the input comes with another parameter $k$. In the first variant, called BPDC, $k$ upper bounds the total number of edges to be added and in the second, called BFPDC, $k$ upper bounds the number of additional edges per face. We prove that both problems are {\sf NP}-complete, the first even for 3-connected graphs of face-degree at most 4 and the second even when $k=1$ on 3-connected graphs of face-degree at most 5. In this paper we give parameterized algorithms for both problems that run in $O(n^{3})+2^{2^{O((kd)^2\log d)}}\cdot n$ steps.
Keywords :
Type de document :
Communication dans un congrès
IPEC: International Symposium on Parameterized and Exact Computation, Sep 2015, Patras, Greece. 10th International Symposium on Parameterized and Exact Computation, LIPIcs (43), pp.30-42, 2015, 〈http://algo2015.upatras.gr/ipec/〉. 〈10.4230/LIPIcs.IPEC.2015.30〉
Domaine :

Littérature citée [15 références]

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01225566
Contributeur : Dimitrios M. Thilikos <>
Soumis le : vendredi 16 mars 2018 - 19:39:05
Dernière modification le : vendredi 16 mars 2018 - 20:17:25

### Fichier

6.pdf
Fichiers produits par l'(les) auteur(s)

### Citation

Clément Requilé, Dimitrios M. Thilikos, Petr A. Golovach. Variants of Plane Diameter Completion. IPEC: International Symposium on Parameterized and Exact Computation, Sep 2015, Patras, Greece. 10th International Symposium on Parameterized and Exact Computation, LIPIcs (43), pp.30-42, 2015, 〈http://algo2015.upatras.gr/ipec/〉. 〈10.4230/LIPIcs.IPEC.2015.30〉. 〈lirmm-01225566〉

### Métriques

Consultations de la notice

## 183

Téléchargements de fichiers