  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.
