A Simple Optimal Binary Representation of Mosaic Floorplans and Baxter Permutations

Details A Simple Optimal Binary Representation of Mosaic Floorplans and Baxter Permutations A Simple Optimal Binary Representation of Mosaic Floorplans and Baxter Permutations

2011-11-21

arxiv.org/abs/1111.4937v2

Computer Science

Data Structures and Algorithms

11 pages, 7 figures

Scientific paper

A "floorplan" is a rectangle subdivided into smaller rectangular sections by horizontal and vertical line segments. Each section in the floorplan is called a "block". Two floorplans are considered equivalent if and only if there is a one-to-one correspondence between the blocks in the two floorplans such that the relative position relationship of the blocks in one floorplan is the same as the relative position relationship of the corresponding blocks in another floorplan. The objects of "Mosaic floorplans" are the same as floorplans, but an alternative definition of equivalence is used. Two mosaic floorplans are considered equivalent if and only if they can be converted to each other by sliding the line segments that divide the blocks. Mosaic floorplans are widely used in VLSI circuit design. An important problem in this area is to find short binary string representations of the set of n-block mosaic floorplans. The best known representation is the "Quarter-State Sequence" which uses 4n bits. This paper introduces a simple binary representation of n-block mosaic floorplan using 3n-3 bits. It has been shown that any binary representation of n-block mosaic floorplans must use at least (3n-o(n)) bits. Therefore, the representation presented in this paper is optimal (up to an additive lower order term). "Baxter permutations" are a set of permutations defined by prohibited subsequences. Baxter permutations have been shown to have one-to-one correspondences to many interesting objects in the so-called "Baxter combinatorial family". In particular, there exists a simple one-to-one correspondence between mosaic floorplans and Baxter permutations. As a result, the methods introduced in this paper also lead to an optimal binary representation of Baxter permutations and all objects in the Baxter combinatorial family.

Affiliated with

Also associated with

No associations

Rating

A Simple Optimal Binary Representation of Mosaic Floorplans and Baxter Permutations 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 A Simple Optimal Binary Representation of Mosaic Floorplans and Baxter Permutations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Simple Optimal Binary Representation of Mosaic Floorplans and Baxter Permutations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-377781