Routing with minimum wire length in the dogleg-free Manhattan model is NP-complete

The present article concentrates on the dogleg-free Manhattan model where h orizontal and vertical wire segments are positioned on different sides of t he board and each net (wire) has at most one horizontal segment. While the minimum width can be found in linear time in the single row routing, appare ntly there was no efficient algorithm to find the minimum wire length. We s how that there is no hope to find such an algorithm because this problem is NP -complete even if each net has only two terminals. The results on dogle g-free Manhattan routing can be connected with other application areas rela ted to interval graphs. In this paper we define the minimum value interval placement problem. There is given a set of weighted intervals and w rows an d the intervals have to be placed without overlapping into rows so that the sum of the interval values, which is the value of a function of the weight and the row number assigned to the interval, is minimum. We show that this problem is NP -complete. This implies the NP -completeness of other proble ms including the minimum wire length routing and the sum coloring on interv al graphs.