Simple and efficient floor-planning

✍ Scribed by Maciej Kurowski

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 238 KB
• Volume: 86
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(02)00490-8

✦ Synopsis

We show a new algorithm for computing in O(n) time a floor-plan of a given plane near-triangulation. We use modules which are the union of two rectangles and are T-, L-or I-shaped. Our algorithm has the following advantages: the number of T-shaped modules is at most 1 2 (n -2), all T-shaped modules are uniformly directed, the size of the picture is at most n × n -1. A very important asset of our algorithm is its extraordinary simplicity.