A Linear-Time Algorithm for the Homotopic Routing Problem in Grid Graphs
Michael Kaufmann, Kurt Mehlhorn · SIAM Journal on Computing · 1994
The paper considers the problem of finding edge-disjoint paths between pairs of vertices in a finite grid graph. The homotopy class for each path to be routed is prespecified. A very fast algorithm that guarantees to find a solution for any solvable homotopic routing problem is given.