Parameterized Algorithm for the Disjoint Path Problem on Planar Graphs: Exponential in $k^2$ and Linear in $n$

Kyungjin Cho, Eunjin Oh, Seunghyeok Oh

In this paper, we study the \textsf{Planar Disjoint Paths} problem: Given an undirected planar graph $G$ with $n$ vertices and a set $T$ of $k$ pairs $(s_i,t_i{)}_{i=1}^k$ of vertice…