The Combinatorial Object Server

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

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]).

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:

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].

Generic rectangulation | Diagonal rectangulation | Block-aligned rectangulation |

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

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.

- none: OEIS A342141 (generic rectangulations [Rea12])
- 3: OEIS A117106 ?
- 34: OEIS A001181 (diagonal rectangulations [CSS18])
- 134/136/145: OEIS A000139 ?
- 345: OEIS A281784 ?
- 1234: OEIS A006318 (slicing floorplans [YCCG03])
- 12345: OEIS A106228 ?
- 123456: OEIS A078482 (1-sided guillotine rectangulations [AM10])
- 123457: OEIS A033321 ?
- 345678: OEIS A000984 ? (central binomial coefficients)
- 1345678: OEIS A026029 ?
- 12345678: OEIS A006012 ?

- none: OEIS A214358 (block-aligned rectangulations [ABBM+13])
- 12: OEIS A078482 (block-aligned guillotine rectangulations [ABBM+13])

- [ABBM+13] A. Asinowski, G. Barequet, M. Bousquet-Mélou, T. Mansour, and R. Y. Pinter. Orders induced by segments in floorplans and (2-14-3, 3-41-2)-avoiding permutations. Electron. J. Combin., 20(2):Paper 35, 43, 2013.
- [AM10] A. Asinowski and T. Mansour. Separable d-permutations and guillotine partitions. Ann. Comb., 14(1):17–43, 2010.
- [CSS18] J. Cardinal, V. Sacristán, and R. I. Silveira. A note on flips in diagonal rectangulations. Discrete Math. Theor. Comput. Sci., 20(2):Paper No. 14, 22, 2018.
- [EMSV12] D. Eppstein, E. Mumford, B. Speckmann, and K. Verbeek. Area-universal and constrained rectangular layouts. SIAM J. Comput., 41(3):537–564, 2012.
- [MM21] A. Merino and T. Mütze. Combinatorial generation via permutation languages. III. Rectangulations. arXiv:2103.09333, March 2021.
- [Rea12] N. Reading. Generic rectangulations. European J. Combin., 33(4):610–623, 2012.
- [YCCG03] B. Yao, H. Chen, C.-K. Cheng, and R. L. Graham. Floorplan representations: Complexity and connections. ACM Trans. Design Autom. Electr. Syst., 8(1):55–80, 2003.