Skip to Main content Skip to Navigation
Conference papers

Variants of Plane Diameter Completion

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

Cited literature [15 references]  Display  Hide  Download
Contributor : Dimitrios Thilikos <>
Submitted on : Friday, March 16, 2018 - 7:39:05 PM
Last modification on : Tuesday, June 30, 2020 - 3:12:02 PM
Document(s) archivé(s) le : Tuesday, September 11, 2018 - 1:15:21 AM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License




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. pp.30-42, ⟨10.4230/LIPIcs.IPEC.2015.30⟩. ⟨lirmm-01225566⟩



Record views


Files downloads