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

Abstract

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,\dots ,Q_k\}$ of vertex-disjoint paths with minimum total length, where $Q_i$ is an $s_i$-to-$t_i$ path between $s_i$ and $t_i$. We consider the problem in planar graphs, where little is known about computational tractability, even in restricted cases. Kobayashi and Sommer propose a polynomial-time algorithm for $k\le 3$ in undirected planar graphs assuming all terminals are adjacent to at most two faces. Colin de Verdiere and Schrijver give a polynomial-time algorithm when all the sources are on the boundary of one face and all the sinks are on the boundary of another face and ask about the existence of a polynomial-time algorithm provided all terminals are on a common face. We make progress toward Colin de Verdiere and Schrijver's open question by giving an $O(k{n}^5)$ time algorithm for undirected planar graphs when $\{(s_1,t_1),\dots ,(s_k,t_k)\}$ are in counter-clockwise order on a common face.

arXiv commentThis is a preliminary version of a paper that will appear in Proceedings of the 23rd European Symposium on Algorithms (ESA 2015), Patras, Greece