Implementations of Undirected Disjoint Paths I'm looking into the Undirected Vertex Disjoint Paths problem:


  Given a list of tuples of vertices (s_i, t_i)
  
  Find simple, pairwise disjoint paths P_{s_0,t_0}, P_{s_1,t_1}, ... that connects the given vertices. If they exist.


I'm in particular interesting in implementing a solution to this this for grid meshes. A situation that comes up in many pen+paper puzzles. I know this will be NP hard in the list of tuples, but hopefully not in the size of the graph.

I know about the Robertson-Seymour theorem, and its complications. However I'm wondering if the required minors might be well known for say planar graphs or meshes?

I also found mentions that Schrijver has made a more approachable polynomial algorithm, but I haven't been able to find mentions of complexity in terms of implementation.

Can anyone point me in a good direction?
I'd be interested even in solutions for just two pairs.
If you want an implementation, Sage has one. With a LP, as usual ;-)

http://www.sagemath.org/doc/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.disjoint_routed_paths

Nathann