Gerrymandering on a high-genus surface/can I use my powers for evil?
Can we not ignore multiplicities of overpasses, at least in the second formulation of the problem? We know that each polygon with a path through it requires at least one overpass. But if we have a polygon with any number of paths through it, such as:
Can we not replace these path segments with a piecewise linear path the goes from one boundary point, which remains the same, to some central overpass, to another boundary point. This would give the following:
Which doesn't affect anything outside of the polygon and reduces all paths inside to one overpass. This gives an upper bound of $mn$.