It seems you are trying to find minimum genus graph embedding, where your nodes are the graph vertices and the required connections are its edges. Minimal genus in your case can be interpreted as minimal number of edge crossings needed. Looking for connections of the minimal lengths makes it even harder (or does it?)
Minimum graph genus itself is NP-complete (in particular its decision version - whether a graph can be embedded in a surface of genus less than k
).
Therefore your problem, if the task would be to find such a path with minimal number of crossings, would be NP-hard as well.
However, if you consider only graphs that are planar, then finding a planar embedding can be done in linear time.