Generic Rectangulations: Enumerative and Structural Aspects

A rectangulation, or a floorplan, is a partition of a rectangle into finitely many interior-disjoint rectangles. The study of rectangulations has been an active research area in the last years, with numerous contributions from different fields of mathematics and computer science. From the combinatorial point of view, rectangulations are a natural structure related to many other well-studied structures, such as trees, maps, permutation classes, lattice paths, etc. For researchers from computational geometry, the interest in rectangulations is motivated primarily by the fact that they are a basic model for integrated circuit layout. Recently, connections between rectangulations and Hopf algebras have been established. Finally, rectangulations are of interest for theoretical foundations of architectural design. The combinatorial analysis of floorplans is a rich and challenging topic. Many naturally arising questions have been answered only for very special cases. Therefore, we propose a research project on some structural and enumerative issues related to rectangulations. The problems that we plan to investigate in the framework of this project deal with exact and asymptotic enumeration of certain classes of rectangulations; their representation by classes of permutations defined by forbidden patterns; structure of reconfiguration graph of rectangulations with respect to different kinds of "flips"; classes of permutations related to Baxter pemutations, which are known to be in bijection with one natural kind of rectangulations, etc. Some of these questions are open problems posed in recent works on this topic. The suggested methodology includes structural analysis and modern methods in analytic and enumerative combinatorics. In particular, the project should emphasize the great potential of modern analytic combinatorics for tackling problems motivated by theoretical computer science. Such methods have been employed rarely in this area so far and we believe that their application in this field will lead to major progress. In addition, we expect that the use of computer algebra and symbolic computation algorithms will play an important role for obtaining experimental data and checking hypotheses, and in some cases lead to new results.

The project focused on the enumerative and structural properties of rectangulations. A rectangulation is a decomposition of a rectangle into smaller rectangles using horizontal and vertical segments. Such decompositions play an important role in the mathematical modeling of VLSI chip design, the visualization of scientific data, geometric algorithms, architectural design, and other areas. From a mathematical point of view, rectangulations form a very natural geometric and combinatorial structure: they are easy to describe and visualize, yet their analysis is challenging. The enumerative aspects address the question of how many essentially different ways a rectangle can be subdivided into a given number of smaller rectangles. In this context, the exact dimensions of the rectangles are irrelevant; instead, only the adjacencies between rectangles and segments are taken into account. For example, a rectangle can be divided into 2 rectangles in exactly two ways (by a horizontal or a vertical cut) and into 3 rectangles in six ways. For larger numbers of rectangles, however, the answer is not readily seen and requires advanced mathematical methods. Moreover, starting with 4 rectangles, two natural notions of enumeration arise: weak rectangulations, which preserve rectangle-segment adjacencies, and strong rectangulations, which preserve rectangle-rectangle adjacencies. The structural aspects concentrate on feasible rectangulations - for instance, representing them by other combinatorial structures such as geometric graphs, partially ordered sets, and permutations. This also includes the topic of pattern avoidance, where one considers rectangulations that do not contain certain local configurations. The main results of the project can be summarized as follows: 1. A uniform representation of weak and strong rectangulations in terms of lattice congruences and classes of permutations. 2. Novel algorithms for mapping from rectangulations to permutations and vice versa. 3. A general framework that unifies, extends, and generalizes numerous earlier contributions. 4. A characterization of strong guillotine rectangulations using mesh patterns. 5. A complete analytic solution for the enumeration of all weak guillotine rectangulation models that were explored algorithmically by Merino and Mütze (2024). 6. The enumeration of all classes of pattern-avoiding rectangulations in which the forbidden patterns are T-shaped configurations of specified orientations, in all possible combinations. 7. Novel bijections between classes of rectangulations and inversion sequences, permutations, and lattice paths. 8. A proof of a conjecture by Yan and Lin (2020) concerning the enumeration of the class I(011,201) of inversion sequences. 9. A characterization of rectangulation patterns involving three segments by mesh patterns and the enumeration of the respective rectangulation models. These results appear in articles co-authored with Jean Cardinal, Stefan Felsner, and Éric Fusy (1-4), Cyril Banderier (5), Michaela Polley (6-8), and Torsten Mütze, Namrata, and Michaela Polley (9).