2026-07-23T00:26:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5569 2024-03-06T10:36:34Z ddc:004 open_access

Variants of Plane Diameter Completion Golovach, Petr A. Requilé, Clément Thilikos, Dimitrios M. Planar graphs graph modification problems parameterized algorithms dynamic programming branchwidth The 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 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)}} * n steps. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Petr A. Golovach and Clément Requilé and Dimitrios M. Thilikos 2015 Is Part Of LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2015.30 urn:nbn:de:0030-drops-55697 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.30 eng https://creativecommons.org/licenses/by/3.0/legalcode