Optimal route between any two points in a planar graph

Question

I am after one algorithm that finds the optimal route between any two points in a floor plan (planar graph). I have attached image to illustrate what I want to achieve. In the image, the goal is to connect the hollow point to any other point and minimize intersections at the same time (no intersection in this case).

in the image above, let's say I also want to connect blue to grey and purple to green, this would introduce an intersection and its what I want to avoid.

So, I just want an algorithm that find the optimal route between any two points in the planar graph, by optimal I mean shortest route with minimum intersections. would be really grateful if anyone can point me in the right direction to make a start.

Answer 1

What you are looking for has seen considerable research in VLSI circuit design and is called Routing (in that context).

This does not have a small answer as there are numerous considerations based on design requirements. Some starting points can be found here.