Compact Floor-Planning via Orderly Spanning Trees
<|reference_start|>Compact Floor-Planning via Orderly Spanning Trees: 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.<|reference_end|>
@article{liao2002compact,
    title={Compact Floor-Planning via Orderly Spanning Trees},
    author={Chien-Chih Liao, Hsueh-I Lu, Hsu-Chun Yen},
    journal={Journal of Algorithms, 48(2):441-451, 2003},
    year={2002},
    doi={10.1016/S0196-6774(03)00057-9},
    archivePrefix={arXiv},
    eprint={cs/0210016},
    primaryClass={cs.DS cs.CG}
}