Shortest Vertex-Disjoint Two-Face Paths in Planar Graphs

ÉRic Colin De VerdiéRe & Alexander Schrijver
Let $G$ be a directed planar graph of complexity~$n$, each arc having a nonnegative length. Let $s$ and~$t$ be two distinct faces of~$G$; let $s_1,ldots,s_k$ be vertices incident with~$s$; let $t_1,ldots,t_k$ be vertices incident with~$t$. We give an algorithm to compute $k$ pairwise vertex-disjoint paths connecting the pairs $(s_i,t_i)$ in~$G$, with minimal total length, in $O(knlog n)$ time.