In this paper, the authors consider a problem to seek a rectangular dual D and its area-efficient drawing such that D can be drawn in the smallest area among all rectangular duals under the constraints imposed not only on the area and the minimum dimension of each face but also on the length of abutment between two adjacent faces. Since the problem is hard to solve, they tackle this problem in an exhaustive manner by using an algorithm to enumerate all the rectangular duals. In order to make this exhaustive method efficient, the authors propose the following two algorithms working under the constraints stated above; an algorithm to find an area-efficient drawing of a given rectangular dual, and an algorithm to estimate a lower bound to the area required to draw a given rectangular dual. They also show some experimental results to demonstrate the effectiveness of the lower bound. The area-efficient drawing of D can be used as a VLSI floor-plan by regarding each inner face of D as an area for a block to be placed.
