minimizing total path cost with obstacles and spatial constraints

Question

I have a network of nodes arranged on a 2D Grid. I want to connect pairs of nodes with connections that will then occupy physical space on the 2D grid. The connections are now obstacles themselves and future connections will have to take a path that avoids intersecting them.

I am currently using the A* algorithm and gradually building up the connection. While it finds the shortest path from start to end node, it does not consider the other connections that will need to be made, so the total path cost after connecting all the pairs is not optimal.

Does anyone know whether there is an algorithm that can solve this, or is this a NP complete problem? Any direction on related material would also be appreciated.

Answer 1

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.