Counting and sampling minimum (s,t)-cuts in weighted planar graphs in polynomial time

We give an O(nd+nlogn) algorithm computing the number of minimum (s,t)-cuts in weighted planar graphs, where n is the number of vertices and d is the length of the shortest s–t path in the corresponding unweighted graph. Previously, Ball and Provan gave a polynomial-time algorithm for unweighted planar graphs with both s and t lying on the outer face. Our results hold for all locations of s and t and weighted graphs, and have direct applications in computer vision.