Floor-Planning via Orderly Spanning Trees

Liao, Chien-Chih and Lu, Hsueh-I. and Yen, Hsu-Chun (2002) Floor-Planning via Orderly Spanning Trees. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001 , pp. 367-377(Official URL: http://dx.doi.org/10.1007/3-540-45848-4_29).

Full text not available from this repository.


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)\times \left\lfloor\frac{2n+1}{3}\right\rfloor.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-45848-4_29
Classifications: G Algorithms and Complexity > G.999 Others
M Methods > M.900 Tree
URI: http://gdea.informatik.uni-koeln.de/id/eprint/527

Actions (login required)

View Item View Item