Parameterized Algorithm for the Disjoint Path Problem on Planar Graphs: Exponential in k2 and Linear in n

Abstract

In this paper, we study the Planar Disjoint Paths problem: Given an undirected planar graph G with n vertices and a set T of k pairs (si, ti)(Equation presented) of vertices, the goal is to find a set P of k pairwise vertex-disjoint paths connecting si and ti for all indices i ∈ {1, ..., k}. We present a (Equation presented)-time algorithm for the Planar Disjoint Paths problem. This improves the two previously best-known algorithms: (Equation presented)-time algorithm [Discrete Applied Mathematics 1995] and (Equation presented)-time algorithm [STOC 2020].