We know that the Utility Problem asks to connect three utilities to three houses without crossing utilities line. I can prove that there is no solution in the plane or $S^2$, but it is solvable on torus.
But, if we're given utilities $U_1, U_2,\dotsc, U_m$ and houses $H_1,H_2, \dotsc, H_n$ located on a sphere with $g$ handles. How can we quickly find necessary and sufficient conditions for $m$, $n$, $g$, so that this problem can be solved?
I tried to start with simple situation but it becomes too complicated as I increase the value of $m$ and $n$.
The complete bipartite graph $K_{m,n}$ (which is the graph for the problem with $m$ utilities that must all be connected to $n$ houses) requires adding $$\gamma(K_{m,n}) = \left\lceil \frac{(m-2)(n-2)}{4} \right\rceil$$ handles to the plane (or, equivalently, to the sphere) before it can be embedded, according to Wolfram MathWorld; the original citation is in German here (Gerhard Ringel, "Das Geschlecht des vollständigen paaren Graphen").