The problem of placing the fewest axial lines of arbitrary orientation
which cross all of the adjacencies in a configuration of nonoverlapping
orthogonal rectangles (ALP-ALOR) has been shown to be NP-Complete.  Work is
currently underway to develop heuristics to produce approximate solutions
for ALP-ALOR and minimal solutions are required to assess the accuracy of
the approximations.

This paper discusses an algorithm, and an implementation thereof,
which produces such minimal solutions.  The algorithm generates every
possible line which could originate from every rectangle in the
configuration of adjacent nonoverlapping rectangles, removes any
redundant lines, to identifies any lines which are essential and thus
have to be in the final solution) and then tests the possible
combinations of choice lines until some combination which crosses all
of the adjacencies is found.