Decomposition of Graphs on Surfaces

✍ Scribed by Maurits de Graaf; Alexander Schrijver

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 266 KB
• Volume: 70
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1997.1747

✦ Synopsis

dedicated to professor w. t. tutte on the occasion of his eightieth birthday Let G=(V, E) be an Eulerian graph embedded on a triangulizable surface S. We show that E can be decomposed into closed curves C 1 , ..., C k such that mincr(G, D)= k i=1 mincr(C i , D) for each closed curve D on S. Here mincr(G, D) denotes the minimum number of intersections of G and D$ (counting multiplicities), where D$ ranges over all closed curves D$ freely homotopic to D and not intersecting V. Moreover, mincr(C, D) denotes the minimum number of intersections of C$ and D$ (counting multiplicities), where C$ and D$ range over all closed curves freely homotopic to C and D, respectively. Decomposing the edges means that C 1 , ..., C k are closed curves in G such that each edge is traversed exactly once by C 1 , ..., C k . So each vertex v is traversed exactly 1 2 deg (v) times, where deg (v) is the degree of v. 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 given 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 # R E homotopic to C 1 , ..., C k respectively such that f 1 (e)+ } } } + f k (e) 1 for each edge e if and only if mincr(G, D) k i=1 mincr(C i , D) for each closed curve D on S. Here a circulation homotopic to a closed curve C 0 is any convex combination of functions tr C # R E , where C is a closed curve in G freely homotopic to C 0 and where tr C (e) is the number of times C traverses e.