Seminar
Ausgewählte Kapitel der Kombinatorik:
Rectangulations

Wintersemester 2025/26
Prof. Stefan Felsner
Sprechstunde n.V.

LV-Nr.: 3236 L 316


Zeichnung

Aktuell:

Die Vorbesprechung findet am Freitag 17. Oktober um 14ct. im MA 875 statt.

Es ist vorgesehen das Seminar als Blockseminar zu veranstalten. Als Termin kommen die Wochenenden Jan. 23-25 oder Feb. 13-15 infrage.

Thema:

A rectangulation is a decomposition of a rectangle into finitely many interior-disjoint rectangles. Rectangulations constitute a classical topic in mathematical tessellation theory. The earliest contributions on the topic may be papers by Abe from early 1930s, a paper by Brooks, Stone, Smith, and Tutte (collectively known as Blanche Descartes) on “squaring the square”.

Questions of counting and generating rectangulations are of combinatorial interest. Representations of (planar) graphs via rectangulations is a topic in graph theory and graph drawing. Rectangulations also have applications in the analysis of geometric algorithms, in visualization of scientific data (for instance treemaps and cartogram), in mathematical foundations of architectural design, and they also appear in visual art — notably in the work of the Dutch art movement De Stijl (see Figure).

In the seminar we will also touch representations of graphs with cubes and other generalizations of rectangulations to 3-D and higher.

Quellen:

  1. Bonichon-d-Baxter.pdf
    Higher dimensional floorplans and Baxter d-permutations
    arxiv.org/abs/2504.01116

  2. Huemer-rect-of-influence.pdf
    4-labelings and grid embeddings of plane quadrangulations
    Lali Barrière and Clemens Huemer
    Discrete Mathematics
    Volume 312, Issue 10, 2012, Pages 1722-1731

  3. Zhang-Rectangle-of-Influence.pdf
    Closed Rectangle-of-Influence Drawings for Irreducible Triangulations
    Sadish Sadasivam & Huaming Zhang
    Computational Geometry
    Volume 44, Issue 1, 2011, Pages 9-19

  4. Kozma-binary-search.pdf
    Binary search trees and rectangulations
    László Kozma and Thatchaphol Saranurak
    (correspondence with the flip-sequence between two rectangulations)
    arxiv.org/abs/1603.08151

  5. Merino-Muetze-PermutLang-Rectang.pdf
    Combinatorial Generation via Permutation Languages. III. Rectangulations
    Arturo Merino, Torsten Mütze
    Discret. Comput. Geom. 70(1): 51-122 (2023)

  6. 67. https://page.math.tu-berlin.de/~felsner/Paper/cubes.pdf
    Contact representations of planar graphs with cubes
    with Mathew C. Francis
    Proceedings SoCG '11, 315-320.

  7. 68. https://page.math.tu-berlin.de/~felsner/Paper/geom-rep.pdf
    Rectangle and Square Representations of Planar Graphs
    in "Thirty Essays in Geometric Graph Theory" edited by J. Pach, 213-248
    Springer New York, 2012

  8. 76. https://page.math.tu-berlin.de/~felsner/Paper/floorp.pdf
    Exploiting Air-Pressure to Map Floorplans on Point Sets
    JGAA 18 (2014) 233-252
    http://jgaa.info/index.php/jgaa/article/view/paper320

  9. On the number of rectangulations of a planar point set.
    E. Ackerman, G. Barequet, and R. Y. Pinter.
    J. Combin. Theory Ser. A, 113(6):1072–1091, 2006
    doi:10.1016/j.jcta.2005.10.003.

  10. 80. https://page.math.tu-berlin.de/~felsner/Paper/new-bt.pdf
    The Order Dimension of Planar Maps Revisited
    SIAM J. Discret. Math. 28 (2014) 1093-1101.

  11. 86. https://page.math.tu-berlin.de/~felsner/Paper/1dR-ecg14.pdf
    Graphs admitting d-realizers: spanning-tree-decompositions and box-representations
    with William Evans Stephen G. Kobourov, and Torsten Ueckerdt
    Proceedings EuroCG 14.

  12. 121. https://page.math.tu-berlin.de/~felsner/Paper/platten.pdf
    Plattenbauten: Touching Rectangles in Space
    with Kolja Knauer and Torsten Ueckerdt
    SIAM Journal of Discrete Mathematics, 39 (2025) 752-782.

  13. 129. https://page.math.tu-berlin.de/~felsner/Paper/aru-lay.pdf
    Aspect Ratio Universal Rectangular Layouts
    with Andrew Nathenson and Csaba D. Tóth
    Computing in Geometry and Topology, 3:1–3:24 (2024).

  14. 137. https://page.math.tu-berlin.de/~felsner/Paper/rectangulations.pdf
    Combinatorics of rectangulations: Old and new bijections
    with Andrej Asinowski, Jean Cardinal, and Éric Fusy
    Combinatorial Theory, 5 (2025) #14.

Zielgruppe:

Studentinnen und Studenten der Mathematik, Techno- und Wirtschaftsmathematik
       Dieses Seminar wird im Rahmen des Studienschwerpunkts Diskrete Strukturen empfohlen.

Zuletzt bearbeitet September 2025