zbMATH — the first resource for mathematics

Floor-planning via orderly spanning trees. (English) Zbl 1054.68597
Mutzel, Petra (ed.) et al., Graph drawing. 9th international symposium, GD 2001, Vienna, Austria, September 23–26, 2001. Revised papers. Berlin: Springer (ISBN 3-540-43309-0). Lect. Notes Comput. Sci. 2265, 367-377 (2002).
Summary: 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$$.
For the entire collection see [Zbl 0984.00060].

MSC:
 68R10 Graph theory (including graph drawing) in computer science 68U05 Computer graphics; computational geometry (digital and algorithmic aspects) 05C85 Graph algorithms (graph-theoretic aspects)
Full Text: