How to connect two points without crossing another path?

Question

Let's pretend I have the following grid. I have to connect pairs of letters. Not only the same letters have to be connected, but I must also make sure that the connecting paths don't cross each other. What's the algorithm that could tell me if it is possible to connect all the pairs without crossing paths and the shortest path?

I realize that this is a graph problem and the shortest path part could be solved using BFS. What I am not sure about is the crossing paths.

  +---+---+---+---+---+---+---+---+
  | A |   |   | B |   |   |   |   |
  +-------------------------------+
  |   |   |   |   |   |   |   |   |
  +-------------------------------+
  |   |   | B |   |   |   | D |   |
  +-------------------------------+
  |   |   |   |   |   |   |   |   |
  +-------------------------------+
  |   | C |   |   | C |   |   |   |
  +-------------------------------+
  |   |   |   | A |   |   |   |   |
  +-------------------------------+
  |   |   |   |   |   |   | D |   |
  +-------------------------------+
  |   |   |   |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+

Answer 1

This is an NP-complete problem called "Disjoint Connecting Paths". Other than some super-polynomial algorithm (really slow), there are some approximation algorithms (might make a mistake, or is non-optimal).

• An Approximation Algorithm for the Disjoint Paths Problem in Even-Degree Planar Graphs - Jonas Kleinberg (pdf)