A note on packing paths in planar graphs

Seymour proved that the cut criterion is necessary and sufficient for the solvability of the edge-disjoint paths problem when the union of the supply graph and the demand graph is planar and Eulerian. When only planarity is required, Middendorf and Pfeiffer proved the problem to be NP-complete. For this case, Korach and Penn proved that the cut criterion is sufficient for the existence of a near-complete packing of paths. Here the authors generalize this result by showing how a natural strengthening of the cut criterion yields better packings of paths. Analogously to Seymour’s approach, the authors actually prove a theorem on packing cuts in an arbitrary graph and then the planar edge-disjoint paths case is obtained by planar dualization. The main result is derived from a theorem of Sebℝ1o on the structure of ¸±1 weightings of a bipartite graph with no negative circuits.