Seymour (1981)proved that the cut criterion is necessary and sufficien
t for the solvability of the edge-disjoint paths problem when the unio
n of the supply graph and the demand graph is planar and Eulerian. Whe
n only planarity is required, Middendorf and Pfeiffer (1993) proved th
e problem to be NP-complete, For this case, Korach and Penn (1992) pro
ved that the cut criterion is sufficient for the existence of a near-c
omplete packing of paths. Here we generalize this result by showing ho
w a natural strengthening of the cut criterion yields better packings
of paths. Analogously to Seymour's approach, we actually prove a theor
em on packing cuts in an arbitrary graph and then the planar edge-disj
oint paths case is obtained by planar dualization, The main result is
derived from a theorem of Sebo (1990) on the structure of +/- 1 weight
ings of a bipartite graph with no negative circuits.