Orthogonal axial line placement in hole free collections of rectangles
Hein Kruger, Ian Douglas Sanders · South African Institute of Computer Scientists and Information Technologists · 2005
Previous research showed that the problem of finding the smallest set of orthogonal axial lines needed to cross all adjacencies between rectangles in a collection of orthogonal rectangles (ALP-OLOR) is NP-Complete. There are, however, some cases where the problem can be solved in polynomial time by mapping adjacencies to intervals on a line and finding a clique cover of the resulting interval graph. In this paper we extend that result and show that ALP-OLOR can be solved in polynomial time for all hole free collections of rectangles as well as for some collections of rectangles with holes.