Combinatorial generation via permutation languages. III: Rectangulations

DOI10.1007/S00454-022-00393-WarXiv2103.09333OpenAlexW3138159625MaRDI QIDQ6156087FDOQ6156087

Authors: Arturo I. Merino, Torsten Mütze 

Publication date: 12 June 2023

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

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.

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

Recommendations

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

zbMATH Keywords

cartogramGray codepolytopeexhaustive generationpermutation patternflip graphgeneric rectangulationfloorplandiagonal rectangulation

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• 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. VI: Binary trees
• Aspect ratio universal rectangular layouts
• Combinatorial generation via permutation languages
• Combinatorial Generation via Permutation Languages. V. Acyclic Orientations
• Rectangulotopes
• Constructive (2,3)-generation: A permutational approach
• A theory of spherical diagrams

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)