Counting Rectangular Drawings or Floorplans in Polynomial Time
A subdivision of a rectangle into rectangular faces with horizontal and vertical line segments is called a rectangular drawing or floorplan. It has been an open problem to determine whether there exist a polynomial time algorithm for computing R(n). We affirmatively solve the problem, that is, we introduce an O(n(4))-time and O(n(3))-space algorithm for R(n). The algorithm is based on a recurrence for R(n), which is the main result of the paper. We also implement our algorithm and computed R(n) for n <= 3000.
rectangular drawing floorplan enumerative combinatorics dynamic programming