Towards single face shortest vertex-disjoint paths in undirected planar graphs

Glencora Borradaile, Amir Nayyeri, Farzad Zafarani

Given $k$ pairs of terminals $\{(s_1,t_1),\dots ,(s_k,t_k)\}$ in a graph $G$, the min-sum $k$ vertex-disjoint paths problem is to find a collection $\{Q_{1}, Q_{2}, \ld…