An Alternative Approach to Counting Minimum (s; t)-cuts in Planar Graphs

Finding and counting minimum cuts in graphs can be useful in image processing and segmentation and in networking systems such as computer or road networks. Researchers have previously developed polynomial-time algorithms to count minimum cuts in planar graphs which utilize the relationship between maximum network flows and minimum cuts. This thesis presents a polynomial-time algorithm to count the number of minimum (s,t)-cuts in a planar graph without first finding a maximum flow. The presented algorithm is dependent on the finding that (s,t)-cuts in a planar graph correlate to certain cycles found in the dual of that graph, which can be efficiently counted