An extended planar algorithm for maximum integral two-flow

Several problems, including the maximum integral two-flow problem, are known to be NP-complete, but efficiently solvable for planar graphs. In this paper, we extend the algorithm for maximum integral two-flow in planar graphs to certain undirected K3,3-free graphs (graphs not containing any subgraph homeomorphic to K3,3). For such graphs, we provide an O(n) algorithm for determining a maximum integral two-flow of a value not less than the value of a maximum two-flow minus two.