Combinatorics of Generic Rectangulations: Enumerative and Structural Aspects

A rectangulation, or a floorplan, is a partition of a rectangle into finitely many interior-disjoint rectangles. From the combinatorial point of view, rectangulations are a natural structure related to many other well-studied structures. 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. The combinatorial analysis of floorplans is challenging. Many naturally arising questions have been answered only for very special cases or not considered at all. 

In this project we focus on some structural and enumerative issues related to rectangulations. The problems that we plan to investigate deal with exact or 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, etc.

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.

Schlagworte: rectangulations, floorplans, planar maps, permutation patterns, lattice paths, bijections, generating functions, enumeration, asymptotics
Kurztitel: Combinatorics of Generic Rectangulations
Zeitraum: 01.10.2020 - 30.09.2022


MitarbeiterInnen Funktion Zeitraum
Andrei Asinowski (intern)
  • Projektleiter/in
  • 01.10.2020 - 30.09.2022


Projekttyp Forschungsförderung (auf Antrag oder Ausschreibung)
Förderungstyp §26
  • Grundlagenforschung
  • 101011 - Graphentheorie
  • 101012 - Kombinatorik
Forschungscluster Kein Forschungscluster ausgewählt
Genderrelevanz Genderrelevanz nicht ausgewählt
  • Science to Science (Qualitätsindikator: I)
Klassifikationsraster der zugeordneten Organisationseinheiten:
Arbeitsgruppen Keine Arbeitsgruppe ausgewählt


Organisation: Fonds zur Förderung der wissenschaftlichen Forschung (FWF)


Keine Partnerorganisation ausgewählt