Generate rectangulations

Generate various classes of rectangulations with $n$ rectangles.
Number $n$ of rectangles (max. 15)
Base type
Forbidden patterns clockwise windmill counterclockwise windmill
left/right brick bottom/top brick
right/left brick top/bottom brick
vertical H horizontal H
Output format
Output  numbering graphics

Object info

A generic rectangulation is a subdivision of a rectangle into $n$ rectangles, such that no four rectangles meet in a point [Rea12]. Diagonal rectangulations are a subset of generic rectangulations, and they have the property that every rectangle intersects the top-left to bottom-right diagonal [CSS18]. Block-aligned rectangulations are a subset of diagonal rectangulations defined in [MM21] (based on the results from [ABBM+13]).
Generic rectangulationDiagonal rectangulationBlock-aligned rectangulation
By forbidding certain patterns of segments in any of these three base classes of rectangulations, we obtain further interesting classes of rectangulations. The eight patterns described in [MM21] and implemented on this website are the following:
1. clockwise windmill 2. counterclockwise windmill
3. left/right brick 4. bottom/top brick
5. right/left brick 6. top/bottom brick
7. vertical H 8. horizontal H
In fact, diagonal rectangulations are obtained by forbidding the left/right brick pattern and the bottom/top brick pattern in generic rectangulations [CSS18]. Furthermore, forbidding the two windmill patterns in generic rectangulations, we obtain so-called guillotine rectangulations, which can be cut into their constituent rectangles by repeated horizontal or vertical straight cuts. Forbidding the two windmill patterns in diagonal rectangulations, we obtain slicing floorplans [YCCG03]. By forbidding all four brick patterns in generic rectangulations, we obtain 1-sided rectangulations, which have been shown to be exactly all area-universal rectangulations, i.e., for any assignment of positive area values to the rectangles, there is a realization of the rectangulation in the plane such that each rectangle has the prescribed area [EMSV12]. Other interesting combinations of patterns have been studied in [AM10, ABBM+13].

In the paper [MM21] we propose a framework for exhaustively generating various classes of rectangulations, including pattern-avoiding rectangulations, and the code running on this website implements the algorithms from this paper. In the text-based output above, each rectangle is specified by its bottom-left and top-right coordinate, and all coordinates are scaled to integers. The algorithmic generation framework is based on encoding rectangulations by permutations, exploiting that many of the aforementioned classes of rectangulations are bijectively equivalent to classes of pattern-avoiding permutations. For example, generic rectangulations are in bijection to 2-clumped permutations [Rea12], and diagonal rectangulations are in bijection to Baxter and twisted Baxter permutations [CSS18]. Most of the OEIS sequences linked below arise as counting sequences for certain pattern-avoiding permutations.

Enumeration (OEIS)

By forbidding certain subsets of the eight aforementioned patterns $\{1,\ldots,8\}$ in generic rectangulations, we obtain rectangulation classes that are counted by the following OEIS sequences. This list shows the subset of forbidden patterns (omitting commas and curly brackets) and the corresponding sequence number. Items marked with ? are conjecturally, and so far have only been observed experimentally. Most combinations of patterns do not appear in the OEIS yet. By doing the same for block-aligned rectangulations as a base class (instead of generic rectangulations), we obtain the following list.

Download source code

[Zipped C++ source code (GNU GPL)]

References