On the solvability of routing multiple point-to-point paths in Manhattan meshes

The solvability of multiple path routing problems in 3D Manhattan meshes is greatly influenced by the order in which the paths are processed. Unsolvable instances can readily be made solvable by simply changing the sequence of paths to be routed, and the inverse also holds. Our results on square meshes with 100 randomly placed terminals show that the routability of an instance can be accurately guessed a priori from its characteristics only. Furthermore, the attainable routability from random sequence change can also be accurately guessed, and a tight scaling relation suggests these results hold for a broad range of instance sizes. For our particulars, the number of routable paths can increase as much as 73%, just by changing the order of processing.