Seminar Rectangulations -- Wintersemester 2025/26

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:

Bonichon-d-Baxter.pdf
Higher dimensional floorplans and Baxter d-permutations
arxiv.org/abs/2504.01116
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
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
Kozma-binary-search.pdf Binary search trees and rectangulations László Kozma and Thatchaphol Saranurak† (correspondence with the flip-sequence between two rectangulations)
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)
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.
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
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
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.
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.
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.
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.
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).
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