Single bend wiring on surfaces

Abstract

The following problem of rectilinear routing is studied: given pairs of points on a surface and a set of permissible orthogonal paths joining them, whether is it possible to choose a path for each pair avoiding all intersections. We prove that if each pair has one or two possible paths to join it, then the problem is solvable in quadratic time, and otherwise it is NP-complete. From that result, we will obtain that the problem of finding a surface of minimum genus on which the wires can be laid out with only one bend is NP-hard.