Compact Floor-Planning via Orderly Spanning Trees

Details Compact Floor-Planning via Orderly Spanning Trees Compact Floor-Planning via Orderly Spanning Trees

2002-10-17

arxiv.org/abs/cs/0210016v2

Journal of Algorithms, 48(2):441-451, 2003

Computer Science

Data Structures and Algorithms

13 pages, 5 figures, An early version of this work was presented at 9th International Symposium on Graph Drawing (GD 2001), Vi

Scientific paper

10.1016/S0196-6774(03)00057-9

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.

Affiliated with

Also associated with

No associations

Rating

Compact Floor-Planning via Orderly Spanning Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Compact Floor-Planning via Orderly Spanning Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compact Floor-Planning via Orderly Spanning Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-671503