Counting Rectangular Drawings or Floorplans in Polynomial Time

Youhei INOUE  Toshihiko TAKAHASHI  Ryo FUJIMAKI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E92-A   No.4   pp.1115-1120
Publication Date: 2009/04/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E92.A.1115
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Advanced Technologies Emerging Mainly from the 21st Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
rectangular drawing,  floorplan,  enumerative combinatorics,  dynamic programming,  

Full Text: PDF>>
Buy this Article



Summary: 
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(n4)-time and O(n3)-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.