  We devise the first constant-factor approximation algorithm for finding an
integral multi-commodity flow of maximum total value for instances where the
supply graph together with the demand edges can be embedded on an orientable
surface of bounded genus. This extends recent results for planar instances. Our
techniques include an uncrossing algorithm, which is significantly more
difficult than in the planar case, a partition of the cycles in the support of
an LP solution into free homotopy classes, and a new rounding procedure for
freely homotopic non-separating cycles.
