2015/09/02 by Petr A. Golovach, Golovach, Petr A., Clément Requilé +3
Computer Science · Engineering · Mathematics · #05C10 #05C85 #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Interconnection Networks and Systems #acm:05C10 #acm:05C85 #acm:68R10 #cs.DS #graph theory and CDMA systems #math.CO #msc:05C10 #msc:05C85 #msc:68R10
paper · pdf · doi:10.48550/arxiv.1509.00757
Accepted in IPEC 2015
arxiv created 2015/09/02 · openalex publication_date 2015/09/02 · arxiv updated 2015/09/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(n3)+2^2O((kd)2log d)⋅ n steps.