Compact Floor-Planning via Orderly Spanning Trees
| dc.creator | Liao, Chien-Chih | |
| dc.creator | Lu, Hsueh-I | |
| dc.creator | Yen, Hsu-Chun | |
| dc.date | 2002-10-17 | |
| dc.date | 2003-05-04 | |
| dc.date.accessioned | 2026-07-07T03:18:56Z | |
| dc.date.available | 2026-07-07T03:18:56Z | |
| dc.description | Floor-planning is a fundamental step in VLSI chip design. Based upon the concept of orderly spanning trees, we present a simple O(n)-time algorithm to construct a floor-plan for any n-node plane triangulation. In comparison with previous floor-planning algorithms in the literature, our solution is not only simpler in the algorithm itself, but also produces floor-plans which require fewer module types. An equally important aspect of our new algorithm lies in its ability to fit the floor-plan area in a rectangle of size (n-1)x(2n+1)/3. Lower bounds on the worst-case area for floor-planning any plane triangulation are also provided in the paper. | |
| dc.description | 13 pages, 5 figures, An early version of this work was presented at 9th International Symposium on Graph Drawing (GD 2001), Vienna, Austria, September 2001. Accepted to Journal of Algorithms, 2003 | |
| dc.identifier | https://arxiv.org/abs/cs/0210016 | |
| dc.identifier | http://arxiv.org/abs/cs/0210016 | |
| dc.identifier | Journal of Algorithms, 48(2):441-451, 2003 | |
| dc.identifier | doi:10.1016/S0196-6774(03)00057-9 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/31317 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Computational Geometry | |
| dc.subject | F.2.2; E.1; G.2.2; B.7.2 | |
| dc.title | Compact Floor-Planning via Orderly Spanning Trees | |
| dc.type | text |