2015/11/16 by Isolde Adler, Adler, Isolde, Stavros G. Kolliopoulos +3
Computer Science · Mathematics · #05C10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Interconnection Networks and Systems #acm:05C10 #cs.DS #math.CO #msc:05C10
paper · pdf · doi:10.48550/arxiv.1511.04952
openalex publication_date 2015/11/16 · arxiv created 2015/11/17 · arxiv updated 2015/11/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
introduce \sc Planar Disjoint Paths Completion, a completion counterpart of the Disjoint Paths problem, and study its parameterized complexity. The problem can be stated as follows: given a, not necessarily connected, plane graph G, k pairs of terminals, and a face F of G, find a minimum-size set of edges, if one exists, to be added inside F so that the embedding remains planar and the pairs become connected by k disjoint paths in the augmented network. Our results are twofold: first, we give an upper bound on the number of necessary additional edges when a solution exists. This bound is a function of k, independent of the size of G. Second, we show that the problem is fixed-parameter tractable, in particular, it can be solved in time f(k)⋅ n2.