Decomposition of graphs on surfaces and a homotopic circulation theorem (Q757396): Difference between revisions

Let G be an eulerian graph, imbedded in a compact orientable surface s, with D a closed curve in S. Let mincr(G,D) denote the minimum number of crossings of G and \(\tilde D,\) among all closed curves \(\tilde D\) homotopic to D and not meeting V(G). Let mincr(C,D) denote the minimum number of crossings of \(\tilde C\) and \(\tilde D,\) among all closed curves \(\tilde C\) and \(\tilde D\) homotopic to C and D, respectively. Then it is shown that E(G) can be decomposed into cycles \(C_ 1,...,C_ t\) so that for each closed curve D in S, \(\min cr(G,D)=\sum^{t}_{i=1}\min cr(C_ i,D).\) The following ``homotopic circulation theorem'', which applies to a problem involving automatic design of integrated circuits posed by K. Mehlhorn, is derived as a corollary: Let G be imbedded in S, with c: E(G)\(\to Q_+\) a ``capacity'' function; let \(C_ 1,...,C_ k\) be cycles in G, with \(d_ 1,...,d_ k\in Q_+\) the corresponding ``demands''. Then there exist circulations \(x_ 1,...,x_ k\) in G such that each \(x_ i\) decomposes fractionally into \(d_ i\) cycles homotopic to \(C_ i\) (1\(\leq i\leq k)\) and such that the total flow through \(e\in E(G)\) is \(\leq c(e)\), for all such e, if and only if: for each closed curve D in S not meeting V(G), the sum of the capacities of the edges intersected by D (counting multiplicities) is at least \(\sum^{k}_{i=1}d_ i\cdot \min cr(C_ i,D)\).