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.