Permutation layout with the minimum number of crossings between wires and the lower horizontal line

Suppose that two sets of terminals t1,t2,...,tm and b1,b2,...,bm are located on two horizontal lines, respectively. Given a permutation ; of integers 1,2,...,m, the permutation layout problem is the problem of finding a single layer routing in which ti and bÅ;Å(iÅ) are connected to each other for i=1,2,...,m. In this paper, the authors study this problem under two constraints: (i) no wire can pass the area above the upper horizontal line, and (ii) no wire can have horizontal zigzagging after crossing the lower horizontal line when starting from the terminal on the upper horizontal line. A dynamic programming algorithm is presented that finds, in O(m²) time, a realization with the minimum number of total crossings between wires and the lower horizontal line. [In Japanese.]