A simple optimal binary representation of mosaic floorplans and Baxter permutations

DOI10.1016/J.TCS.2013.05.007MaRDI QIDQ2445870zbMATH OpenOpenAlexFDO

Authors Bryan Dawei He

Publication date 15 April 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.4937

zbMATH Keywords

Baxter permutationbinary representationfloorplanmosaic floorplan

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial aspects of tessellation and tiling problems (05B45) Combinatorics in computer science (68R05)

Abstract: 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.

Recommendations

• Optimal binary representation of mosaic floorplans and Baxter permutations
• A bijection between permutations and floorplans, and its applications
• Subclasses of Baxter permutations based on pattern avoidance
• Orders induced by segments in floorplans and (2-14-3, 3-41-2)-avoiding permutations
• A (4n − 4)-Bit Representation of a Rectangular Drawing or Floorplan

Cites work

• A (4n − 4)-Bit Representation of a Rectangular Drawing or Floorplan
• A bijection between permutations and floorplans, and its applications
• A Compact Encoding of Rectangular Drawings with Efficient Query Supports
• Algebraic and combinatorial structures on Baxter permutations
• Aztec diamonds and Baxter permutations
• Baxter permutations
• Baxter permutations and plane bipolar orientations
• scientific article; zbMATH DE number 49142 (Why is no real title available?)
• scientific article; zbMATH DE number 2080983 (Why is no real title available?)
• On Fixed Points of the Composite of Commuting Functions
• The quarter-state-sequence floorplan representation

Cited in

(15)

• Orders induced by segments in floorplans and (2-14-3, 3-41-2)-avoiding permutations
• A transformation algorithm to construct a rectangular floorplan
• A bijection between permutations and floorplans, and its applications
• Optimal binary representation of mosaic floorplans and Baxter permutations
• Rectilinear duals using monotone staircase polygons
• Transformations among rectangular partitions
• Enumeration and asymptotic formulas for rectangular partitions of the hypercube
• Subclasses of Baxter permutations based on pattern avoidance
• Uniqueness of rectangularly dualizable graphs
• Combinatorial generation via permutation languages. III: Rectangulations
• Rectangulotopes
• Efficient generation of rectangulations via permutation languages
• Succinct data structures for Baxter permutation and related families
• Closure operations on picture languages and their relation to floor plans
• Constrained floorplans in 2D and 3D

This page was built for publication: A simple optimal binary representation of mosaic floorplans and Baxter permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2445870)