Combinatorial generation via permutation languages. III: Rectangulations
From MaRDI portal
Publication:6156087
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
Cites work
- scientific article; zbMATH DE number 2080983 (Why is no real title available?)
- A Survey of Combinatorial Gray Codes
- 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
- 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
- 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 Hopf algebra of diagonal rectangulations.
- The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
- The greedy Gray code algorithm
- Transversal structures on triangulations: A combinatorial study and straight-line drawings
Cited in
(9)- Combinatorial generation via permutation languages
- Combinatorial generation via permutation languages. VI: Binary trees
- Aspect ratio universal rectangular layouts
- Pivot Gray codes for the spanning trees of a graph ft. the fan
- Counting and Generating Permutations Using Timed Languages
- Combinatorial Generation via Permutation Languages. V. Acyclic Orientations
- Constructive (2,3)-generation: A permutational approach
- A theory of spherical diagrams
- Rectangulotopes
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)
