Shortest vertex-disjoint two-face paths in planar graphs

摘要

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 with s; let t_1, ?, t_k be vertices incident with t. We give an algorithm to compute k pairwise vertex-disjoint paths connecting the pairs (si, ti) in G, with minimal total length, in O(knlog n) time.