DECOMPOSITION OF GRAPHS ON SURFACES

Let G = (V, E) be an Eulerian graph embedded on a triangulizable surfa ce S. We show that E can be decomposed into closed curves C-1,.... C-k such that mincr(G,D) = Sigma(i=1)(k) mincr(C-i, D) for each closed cu rve D on S. Here mincr(G, D) denotes the minimum number of intersectio ns of C and D' (counting multiplicities), where D' ranges over all clo sed curves DI freely homotopic to D and not intersecting V. Moreover, mincr(C, D) denotes the minimum number of intersections oi C' and D' ( counting multiplicities), where C' and D' range over all closed curves freely homotopic to C and D: respectively. Decomposing the edges mean s that C-l...., C-k are closed curves in G such that each edge is trav ersed exactly once by C-l...., C-k. So each vertex upsilon is traverse d exactly 1/2 deg (upsilon) times, where deg (upsilon) is the degree o f upsilon. This result was shown by Lins for the projective plane and by Schrijver for compact orientable surfaces. The present paper gives a shorter proof than the one given for compact orientable surfaces. We derive the following fractional packing result for closed curves of g iven homotopies in a graph G = (V, E) on a compact surface S. Let C-1, ..., C-k be closed curves on S. Then there exist circulations f(1), .. .., f(k) is an element of R-E homotopic to C-1,..., C-k respectively s uch that f(1)(c) +...+ f(k)(e) less than or equal to 1 For each edge e if and only if mincr(G, D) greater than or equal to Sigma(i=1)(k) min cr(C-i, D) For each closed curve D on S. Here a circulation homotopic to a closed curve C-0, is ally convex combination of functions tr(C) i s an element of R-E, where C is a closed curve in G freely homotopic t o C-0 and where tr(C)(e) is the number of times C traverses e. (C) 199 7 Academic Press.