A NOTE ON PACKING PATHS IN PLANAR GRAPHS

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.