Few Sequence Pairs Suffice: Representing All Rectangle Placements

Abstract

We consider representations of general non-overlapping placements of rectangles by spatial relations (west, south, east, north) of pairs of rectangles. We call a set of representations complete if it contains a representation of every placement of $n$ rectangles. We prove a new upper bound of $\mathcal{O}(\frac{n!}{n^6}\cdot (\frac{11+5\sqrt{5}}{2}{)}^n)$ and a new lower bound of $\Omega (\frac{n!}{n^4}\cdot (4+2\sqrt{2}{)}^n)$ on the minimum cardinality of complete sets of representations. A key concept in the proofs of these results are pattern-avoiding permutations. The new upper bound directly improves upon the well-known sequence pair representation, which has size $(n!{)}^2$, by only considering a restricted set of sequence pairs. It implies theoretically faster algorithms for VLSI placement problems.