A simple optimal binary representation of mosaic floorplans and Baxter permutations

摘要

Mosaic floorplans are rectangular structures subdivided into smaller rectangular sections and are widely used in VLSI circuit design. Baxter permutations are a set of permutations that have been shown to have a one-to-one correspondence to objects in the Baxter combinatorial family, which includes mosaic floorplans. An important problem in this area is to find short binary string representations of the set of n-block mosaic floorplans and Baxter permutations of length n. 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).