{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T19:30:29Z","timestamp":1773171029648,"version":"3.50.1"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,11,4]],"date-time":"2022-11-04T00:00:00Z","timestamp":1667520000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,11,4]],"date-time":"2022-11-04T00:00:00Z","timestamp":1667520000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["413902284"],"award-info":[{"award-number":["413902284"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura Cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["GA 19-08554S1"],"award-info":[{"award-number":["GA 19-08554S1"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002847","name":"Ministerio de Educaci\u00f3n, Gobierno de Chile","doi-asserted-by":"publisher","award":["2019-72200522"],"award-info":[{"award-number":["2019-72200522"]}],"id":[{"id":"10.13039\/501100002847","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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.<\/jats:p>","DOI":"10.1007\/s00454-022-00393-w","type":"journal-article","created":{"date-parts":[[2022,11,4]],"date-time":"2022-11-04T21:03:56Z","timestamp":1667595836000},"page":"51-122","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Combinatorial Generation via Permutation Languages. III. Rectangulations"],"prefix":"10.1007","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1728-6936","authenticated-orcid":false,"given":"Arturo","family":"Merino","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6383-7436","authenticated-orcid":false,"given":"Torsten","family":"M\u00fctze","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,11,4]]},"reference":[{"issue":"12","key":"393_CR1","doi-asserted-by":"publisher","first-page":"1674","DOI":"10.1016\/j.dam.2006.03.018","volume":"154","author":"E Ackerman","year":"2006","unstructured":"Ackerman, E., Barequet, G., Pinter, R.Y.: A bijection between permutations and floorplans, and its applications. Discret. Appl. Math. 154(12), 1674\u20131684 (2006)","journal-title":"Discret. Appl. Math."},{"key":"393_CR2","doi-asserted-by":"crossref","unstructured":"Ackerman, E., Barequet, G., Pinter, R.Y.: On the number of rectangulations of a planar point set. J. Combin. Theory Ser. A 113(6), 1072\u20131091 (2006)","DOI":"10.1016\/j.jcta.2005.10.003"},{"key":"393_CR3","unstructured":"Amano, K., Nakano, S., Yamanaka, K.: On the number of rectangular drawings: exact counting and lower and upper bounds. Technical Report #\u00a02007-AL-115. IPSJ SIG (2007)"},{"key":"393_CR4","doi-asserted-by":"crossref","unstructured":"Asinowski, A., Barequet, G., Bousquet-M\u00e9lou, M., Mansour, T., Pinter, R.Y.: Orders induced by segments in floorplans and $$(2-14-3, 3-41-2)$$-avoiding permutations. Electron. J. Combin. 20(2), #\u00a035 (2013)","DOI":"10.37236\/2607"},{"issue":"1","key":"393_CR5","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/s00026-010-0043-8","volume":"14","author":"A Asinowski","year":"2010","unstructured":"Asinowski, A., Mansour, T.: Separable $$d$$-permutations and guillotine partitions. Ann. Combin. 14(1), 17\u201343 (2010)","journal-title":"Ann. Combin."},{"issue":"1\u20133","key":"393_CR6","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0166-218X(95)00026-N","volume":"65","author":"D Avis","year":"1996","unstructured":"Avis, D., Fukuda, K.: Reverse search for enumeration. Discret. Appl. Math. 65(1\u20133), 21\u201346 (1996)","journal-title":"Discret. Appl. Math."},{"issue":"9","key":"393_CR7","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1145\/360336.360343","volume":"19","author":"JR Bitner","year":"1976","unstructured":"Bitner, J.R., Ehrlich, G., Reingold, E.M.: Efficient generation of the binary reflected Gray code and its applications. Commun. ACM 19(9), 517\u2013521 (1976)","journal-title":"Commun. ACM"},{"issue":"4","key":"393_CR8","doi-asserted-by":"publisher","first-page":"2795","DOI":"10.1137\/17M1126734","volume":"32","author":"M Bouvel","year":"2018","unstructured":"Bouvel, M., Guerrini, V., Rechnitzer, A., Rinaldi, S.: Semi-Baxter and strong-Baxter: two relatives of the Baxter sequence. SIAM J. Discret. Math. 32(4), 2795\u20132819 (2018)","journal-title":"SIAM J. Discret. Math."},{"key":"393_CR9","unstructured":"Cardinal, J., Sacrist\u00e1n, V., Silveira, R.I.: A note on flips in diagonal rectangulations. Discret. Math. Theor. Comput. Sci. 20(2), # 14 (2018)"},{"issue":"1","key":"393_CR10","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s00026-013-0209-2","volume":"18","author":"J Conant","year":"2014","unstructured":"Conant, J., Michaels, T.: On the number of tilings of a square by rectangles. Ann. Combin. 18(1), 21\u201334 (2014)","journal-title":"Ann. Combin."},{"key":"393_CR11","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1145\/321765.321781","volume":"20","author":"G Ehrlich","year":"1973","unstructured":"Ehrlich, G.: Loopless algorithms for generating permutations, combinations, and other combinatorial configurations. J. Assoc. Comput. Mach. 20, 500\u2013513 (1973)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"3","key":"393_CR12","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1137\/110834032","volume":"41","author":"D Eppstein","year":"2012","unstructured":"Eppstein, D., Mumford, E., Speckmann, B., Verbeek, K.: Area-universal and constrained rectangular layouts. SIAM J. Comput. 41(3), 537\u2013564 (2012)","journal-title":"SIAM J. Comput."},{"key":"393_CR13","doi-asserted-by":"crossref","unstructured":"Felsner, S.: Rectangle and square representations of planar graphs. In: Thirty Essays on Geometric Graph Theory, pp. 213\u2013248. Springer, New York (2013)","DOI":"10.1007\/978-1-4614-0110-0_12"},{"issue":"3","key":"393_CR14","doi-asserted-by":"publisher","first-page":"993","DOI":"10.1016\/j.jcta.2010.03.017","volume":"118","author":"S Felsner","year":"2011","unstructured":"Felsner, S., Fusy, \u00c9., Noy, M., Orden, D.: Bijections for Baxter families and related objects. J. Combin. Theory Ser. A 118(3), 993\u20131020 (2011)","journal-title":"J. Combin. Theory Ser. A"},{"key":"393_CR15","doi-asserted-by":"crossref","unstructured":"Fujimaki, R., Inoue, Y., Takahashi, T.: An asymptotic estimate of the numbers of rectangular drawings or floorplans. In: 2009 IEEE International Symposium on Circuits and Systems (Taipei 2009), pp. 856\u2013859. IEEE, Los Alamitos (2009)","DOI":"10.1109\/ISCAS.2009.5117891"},{"key":"393_CR16","doi-asserted-by":"crossref","unstructured":"Felsner, S., Nathenson, A., T\u00f3th, C.D.: Aspect ratio universal rectangular layouts (2021). arXiv:2112.03242","DOI":"10.1007\/978-3-030-96731-4_7"},{"issue":"7","key":"393_CR17","doi-asserted-by":"publisher","first-page":"1870","DOI":"10.1016\/j.disc.2007.12.093","volume":"309","author":"\u00c9 Fusy","year":"2009","unstructured":"Fusy, \u00c9.: Transversal structures on triangulations: a combinatorial study and straight-line drawings. Discret. Math. 309(7), 1870\u20131894 (2009)","journal-title":"Discret. Math."},{"key":"393_CR18","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.tcs.2013.05.007","volume":"532","author":"BD He","year":"2014","unstructured":"He, B.D.: A simple optimal binary representation of mosaic floorplans and Baxter permutations. Theoret. Comput. Sci. 532, 40\u201350 (2014)","journal-title":"Theoret. Comput. Sci."},{"key":"393_CR19","unstructured":"Hong, X., Huang, G., Cai, Y., Gu, J., Dong, S., Cheng, Ch.-K., Gu, J.: Corner block list: an effective and efficient topological representation of non-slicing floorplan. In: IEEE\/ACM International Conference on Computer-Aided Design (San Jose 2000), pp. 8\u201312. IEEE, New York (2000)"},{"key":"393_CR20","doi-asserted-by":"crossref","unstructured":"Hartung, E., Hoang, H.P., M\u00fctze, T., Williams, A.: Combinatorial generation via permutation languages. In: 31st Symposium on Discrete Algorithms (Salt Lake City 2020), pp. 1214\u20131225. SIAM, Philadelphia (2020)","DOI":"10.1137\/1.9781611975994.74"},{"issue":"4","key":"393_CR21","doi-asserted-by":"publisher","first-page":"2255","DOI":"10.1090\/tran\/8199","volume":"375","author":"E Hartung","year":"2022","unstructured":"Hartung, E., Hoang, H., M\u00fctze, T., Williams, A.: Combinatorial generation via permutation languages. I. Fundamentals. Trans. Am. Math. Soc. 375(4), 2255\u20132291 (2022)","journal-title":"Trans. Am. Math. Soc."},{"issue":"1","key":"393_CR22","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/s11856-021-2186-1","volume":"244","author":"HP Hoang","year":"2021","unstructured":"Hoang, H.P., M\u00fctze, T.: Combinatorial generation via permutation languages. II. Lattice congruences. Isr. J. Math. 244(1), 359\u2013417 (2021)","journal-title":"Isr. J. Math."},{"issue":"4","key":"393_CR23","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1587\/transfun.E92.A.1115","volume":"92\u2013A","author":"Y Inoue","year":"2009","unstructured":"Inoue, Y., Takahashi, T., Fujimaki, R.: Counting rectangular drawings or floorplans in polynomial time. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 92\u2013A(4), 1115\u20131120 (2009)","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"issue":"1\u20132","key":"393_CR24","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/S0304-3975(95)00257-X","volume":"172","author":"G Kant","year":"1997","unstructured":"Kant, G., He, X.: Regular edge labeling of $$4$$-connected plane graphs and its applications in graph drawing problems. Theoret. Comput. Sci. 172(1\u20132), 175\u2013193 (1997)","journal-title":"Theoret. Comput. Sci."},{"key":"393_CR25","unstructured":"Knuth, D.E.: The Art of Computer Programming. Vol.\u00a04A: Combinatorial Algorithms. Part\u00a01. Addison-Wesley, Upper Saddle River (2011)"},{"issue":"3","key":"393_CR26","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/j.comgeo.2006.06.002","volume":"37","author":"M van Kreveld","year":"2007","unstructured":"van Kreveld, M., Speckmann, B.: On rectangular cartograms. Comput. Geom. 37(3), 175\u2013187 (2007)","journal-title":"Comput. Geom."},{"issue":"3","key":"393_CR27","doi-asserted-by":"publisher","first-page":"788","DOI":"10.1016\/j.jcta.2011.09.006","volume":"119","author":"S Law","year":"2012","unstructured":"Law, S., Reading, N.: The Hopf algebra of diagonal rectangulations. J. Combin. Theory Ser. A 119(3), 788\u2013824 (2012)","journal-title":"J. Combin. Theory Ser. A"},{"key":"393_CR28","unstructured":"Leifheit, L.J.: Combinatorial Properties of Rectangulations. MSc thesis, Technische Universit\u00e4t Berlin (2021)"},{"key":"393_CR29","unstructured":"Meehan, E.: The Hopf algebra of generic rectangulations (2019). arXiv:1903.09874"},{"key":"393_CR30","unstructured":"Merino, A., M\u00fctze, T.: Efficient generation of rectangulations via permutation languages. In: 37th International Symposium on Computational Geometry. Leibniz Int. Proc. Inform., vol. 189, #\u00a054. Leibniz-Zent. Inform., Wadern (2021)"},{"issue":"1","key":"393_CR31","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1068\/b030037","volume":"3","author":"WJ Mitchell","year":"1976","unstructured":"Mitchell, W.J., Steadman, J.P., Liggett, R.S.: Synthesis and optimization of small rectangular floor plans. Environ. Plan. B 3(1), 37\u201370 (1976)","journal-title":"Environ. Plan. B"},{"key":"393_CR32","doi-asserted-by":"crossref","unstructured":"Nakano, S.: Enumerating floorplans with $$n$$ rooms. In: Algorithms and Computation (Christchurch 2001). Lecture Notes in Computer Science, vol. 2223, pp. 107\u2013115. Springer, Berlin (2001)","DOI":"10.1007\/3-540-45678-3_10"},{"key":"393_CR33","doi-asserted-by":"crossref","unstructured":"Otten, R.H.J.M.: Automatic floorplan design. In: 19th Design Automation Conference (Las Vegas 1982), pp. 261\u2013267. IEEE, Los Alamitos (1982)","DOI":"10.1109\/DAC.1982.1585510"},{"key":"393_CR34","unstructured":"Padrol, A., Pilaud, V., Ritter, J.: Shard polytopes. S\u00e9m. Lothar. Combin. 85B, # 11 (2021)"},{"issue":"3","key":"393_CR35","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1112\/blms.12231","volume":"51","author":"V Pilaud","year":"2019","unstructured":"Pilaud, V., Santos, F.: Quotientopes. Bull. Lond. Math. Soc. 51(3), 406\u2013420 (2019)","journal-title":"Bull. Lond. Math. Soc."},{"issue":"4","key":"393_CR36","doi-asserted-by":"publisher","first-page":"610","DOI":"10.1016\/j.ejc.2011.11.004","volume":"33","author":"N Reading","year":"2012","unstructured":"Reading, N.: Generic rectangulations. Eur. J. Combin. 33(4), 610\u2013623 (2012)","journal-title":"Eur. J. Combin."},{"key":"393_CR37","doi-asserted-by":"crossref","unstructured":"Ruskey, F.: Combinatorial Gray code. In: Encyclopedia of Algorithms, pp. 342\u2013347. Springer, New York (2016)","DOI":"10.1007\/978-1-4939-2864-4_732"},{"issue":"4","key":"393_CR38","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1137\/S0036144595295272","volume":"39","author":"C Savage","year":"1997","unstructured":"Savage, C.: A survey of combinatorial Gray codes. SIAM Rev. 39(4), 605\u2013629 (1997)","journal-title":"SIAM Rev."},{"issue":"10","key":"393_CR39","doi-asserted-by":"publisher","first-page":"1354","DOI":"10.1109\/TCAD.2003.818136","volume":"22","author":"ZC Shen","year":"2003","unstructured":"Shen, Z.C., Chu, C.C.N.: Bounds on the number of slicing, mosaic, and general floorplans. IEEE Trans. Comput.-Aid. Des. Integr. Circuits Syst. 22(10), 1354\u20131361 (2003)","journal-title":"IEEE Trans. Comput.-Aid. Des. Integr. Circuits Syst."},{"issue":"4","key":"393_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/scj.10563","volume":"35","author":"M Takagi","year":"2004","unstructured":"Takagi, M., Nakano, S.: Listing all rectangular drawings with certain properties. Syst. Comput. Jpn. 35(4), 1\u20138 (2004)","journal-title":"Syst. Comput. Jpn."},{"key":"393_CR41","doi-asserted-by":"crossref","unstructured":"Williams, A.: The greedy Gray code algorithm. In: 13th International Symposium on Algorithms and Data Structures (London 2013). Lecture Notes in Computer Science, vol. 8037, pp. 525\u2013536. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-642-40104-6_46"},{"issue":"9","key":"393_CR42","doi-asserted-by":"publisher","first-page":"1392","DOI":"10.1587\/transfun.E101.A.1392","volume":"101\u2013A","author":"K Yamanaka","year":"2018","unstructured":"Yamanaka, K., Rahman, M.S., Nakano, A.: Enumerating floorplans with columns. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 101\u2013A(9), 1392\u20131397 (2018)","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"issue":"1","key":"393_CR43","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1145\/606603.606607","volume":"8","author":"B Yao","year":"2003","unstructured":"Yao, B., Chen, H., Cheng, Ch.-K., Graham, R.L.: Floorplan representations: complexity and connections. ACM Trans. Des. Autom. Electr. Syst. 8(1), 55\u201380 (2003)","journal-title":"ACM Trans. Des. Autom. Electr. Syst."},{"issue":"9","key":"393_CR44","doi-asserted-by":"publisher","first-page":"2445","DOI":"10.1093\/ietfec\/e89-a.9.2445","volume":"89\u2013A","author":"S Yoshii","year":"2006","unstructured":"Yoshii, S., Chigira, D., Yamanaka, K., Nakano, S.: Constant time generation of rectangular drawings with exactly $$n$$ faces. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 89\u2013A(9), 2445\u20132450 (2006)","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"393_CR45","unstructured":"The Combinatorial Object Server: Generate Rectangulations. http:\/\/www.combos.org\/rect"},{"key":"393_CR46","unstructured":"The On-Line Encyclopedia of Integer Sequences (2020). http:\/\/oeis.org"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00393-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-022-00393-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00393-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,6]],"date-time":"2023-06-06T18:54:15Z","timestamp":1686077655000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-022-00393-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,4]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["393"],"URL":"https:\/\/doi.org\/10.1007\/s00454-022-00393-w","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,4]]},"assertion":[{"value":"22 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 November 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 December 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 November 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}