Planar Multicommodity Flows, Max Cut, and the Chinese Postman Problem

摘要

For planar graphs, Seymour proved that there is a multicommodity flow if and only if there i no negative cut. Matsumoto et al. have shown how to find the flow by solving O(n) matching problems in a graph with n nodes. Our aim is to point out that the flow can be found by solving a single Chinese Postiman problem in the dual graph and that the problem can be sovled in O(n~3/2 log N) time. The same ideas apply to the max cut problem in planar graphs. We also give a simple algorithmic proof of Seymour's theorem on T-joins.