Combinatorial generation via permutation languages. III: Rectangulations

DOI10.1007/S00454-022-00393-WMaRDI QIDQ6156087zbMATH OpenOpenAlexFDO

Authors Arturo I. Merino, Torsten Mütze

Publication date 12 June 2023

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2103.09333

zbMATH Keywords

cartogramdiagonal rectangulationexhaustive generationflip graphfloorplangeneric rectangulationGray codepermutation patternpolytope

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Discrete geometry (52C99) Combinatorics in computer science (68R05)

Abstract: A generic rectangulation is a partition of a rectangle into finitely many interior-disjoint rectangles, such that no four rectangles meet in a point. In this work we present a versatile algorithmic framework for exhaustively generating a large variety of different classes of generic rectangulations. Our algorithms work under very mild assumptions, and apply to a large number of rectangulation classes known from the literature, such as generic rectangulations, diagonal rectangulations, 1-sided/area-universal, block-aligned rectangulations, and their guillotine variants, including aspect-ratio-universal rectangulations. They also apply to classes of rectangulations that are characterized by avoiding certain patterns, and in this work we initiate a systematic investigation of pattern avoidance in rectangulations. Our generation algorithms are efficient, in some cases even loopless or constant amortized time, i.e., each new rectangulation is generated in constant time in the worst case or on average, respectively. Moreover, the Gray codes we obtain are cyclic, and sometimes provably optimal, in the sense that they correspond to a Hamilton cycle on the skeleton of an underlying polytope. These results are obtained by encoding rectangulations as permutations, and by applying our recently developed permutation language framework.

Recommendations

• Generic rectangulations
• Combinatorial generation via permutation languages
• Combinatorial generation via permutation languages. I: Fundamentals
• scientific article; zbMATH DE number 7641239

Cites work

• A bijection between permutations and floorplans, and its applications
• A note on flips in diagonal rectangulations
• A simple optimal binary representation of mosaic floorplans and Baxter permutations
• A Survey of Combinatorial Gray Codes
• Area-universal and constrained rectangular layouts
• Aspect ratio universal rectangular layouts
• Bijections for Baxter families and related objects
• Combinatorial generation via permutation languages
• Combinatorial generation via permutation languages. I: Fundamentals
• Combinatorial generation via permutation languages. II. Lattice congruences
• Efficient generation of the binary reflected gray code and its applications
• Generic rectangulations
• scientific article; zbMATH DE number 2080983 (Why is no real title available?)
• Loopless Algorithms for Generating Permutations, Combinations, and Other Combinatorial Configurations
• On rectangular cartograms
• On the number of rectangulations of a planar point set
• On the number of tilings of a square by rectangles
• Orders induced by segments in floorplans and (2-14-3, 3-41-2)-avoiding permutations
• Quotientopes
• Rectangle and Square Representations of Planar Graphs
• Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems
• Reverse search for enumeration
• Semi-Baxter and strong-Baxter: two relatives of the Baxter sequence
• Separable \(d\)-permutations and guillotine partitions
• Shard polytopes
• The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
• The greedy Gray code algorithm
• The Hopf algebra of diagonal rectangulations.
• Transversal structures on triangulations: A combinatorial study and straight-line drawings

Cited in

(15)

• Constructive (2,3)-generation: A permutational approach
• Combinatorial generation via permutation languages
• Counting and Generating Permutations Using Timed Languages
• Combinatorial Generation via Permutation Languages. V. Acyclic Orientations
• A theory of spherical diagrams
• Pivot Gray codes for the spanning trees of a graph ft. the fan
• Aspect ratio universal rectangular layouts
• Combinatorial generation via permutation languages. VI: Binary trees
• Rectangulotopes
• Patterns in rectangulations. I: -like patterns, inversion sequence classes I(010, 101, 120, 201) and I(011, 201), and rushed Dyck paths
• Shortest paths on polymatroids and hypergraphic polytopes
• Flips in colorful triangulations
• Pattern-avoiding binary trees -- generation, counting, and bijections
• Combinatorics of rectangulations: old and new bijections
• Combinatorial generation via permutation languages. IV: Elimination trees

This page was built for publication: Combinatorial generation via permutation languages. III: Rectangulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6156087)