Improved Approximation for Node-Disjoint Paths in Planar Graphs

Julia Chuzhoy, David H. K. Kim, Shi Li

We study the classical Node-Disjoint Paths (NDP) problem: given an $n$-vertex graph $G$ and a collection $M=\{(s_1,t_1),\dots ,(s_k,t_k)\}$ of pairs of vertices of $G$ called deman…