Routing through a generalized switchbox

We present an algorithm for the routing problem for two-terminal nets in generalized switchboxes. A generalized switchbox is any subset R of the planar rectangular grid with no nontrivial holes, i.e., every finite face has exactly four incident vertices. A net is a pair of nodes of nonmaximal degree on the boundary of R. A solution is a set of edge-disjoint paths, one for each net. Our algorithm solves standard generalized switchbox routing problems in time O(n(log n)²) where n is the number of vertices of R, i.e., it either finds a solution or indicates that there is none. A problem is standard if deg(ν) + ter(ν) is even for all vertices ν where deg(ν) is the degree of ν and ter(ν) is the number of nets which have ν as a terminal. For nonstandard problems we can find a solution in time O(n(log n)² + |U|²) where U is the set of vertices ν with deg(ν) + ter(ν) is odd.