The  maximum disjoint subset (MDS)  of rectangles is a subset of non-overlapping rectangles with the maximum total weight. The problem of finding the  MDS  of general rectangles has been proven to be NP-complete in [6]. In this paper, we focus on the problem of finding the  MDS  of boundary rectangles, which is an open problem and is closely related to some difficult problems in PCB routing. We propose a polynomial time algorithm to optimally solve the  MDS  problem of boundary rectangles. Then we show that this algorithm can be applied to find the optimal solution of the bus escape routing problem.
['Hui Kong', 'Q. M. Ma', 'Tan Yan', 'Martin D. F. Wong']
An optimal algorithm for finding disjoint rectangles and its application to PCB routing