Shortest Vertex-Disjoint Two-Face Paths in Planar Graphs

Eric 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,...,s_k$ be vertices incident wit…