Rectangular Duals on the Cylinder and the Torus
2025
Read Rectangular Duals on the Cylinder and the Torus (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-07170.txt.
Introduction
Therese Biedl, Philipp Kindermann, and Jonathan Klawitter study a tiling puzzle in graph theory, in a 2025 paper. A rectangular dual draws a graph as a set of touching rectangles, one per point, with no gaps and no four meeting at a corner. Classic work covers flat drawings; they ask what happens on a cylinder or a doughnut-shaped torus.
For the cylinder, they fully settle which graphs admit such a tiling. For the torus, given a labeling that says how rectangles should touch, they can test for a tiling that respects the drawing on a flat torus. Their tests and building steps both run efficiently.
Catalog record
| YEAR | 2025 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 95 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-07170
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Rectangular Duals on the Cylinder and the Torus Abstract A rectangular dual of a plane graph G G is a contact representation of G G by interior-disjoint rectangles such that (i) no four rectangles share a point, and (ii) the union of all rectangles is a rectangle. In this paper, we study rectangular duals of graphs that are embedded in surfaces other than the plane. In particular, we fully characterize when a graph embedded on a cylinder admits a cylindrical rectangular dual. For graphs embedded on the flat torus, we can test whether the graph has a toroidal rectangular dual if we are additionally given a regular edge labeling , i.e. a combinatorial description of rectangle adjacencies. Furthermore we can test whether there exists a toroidal rectangular dual that respects the embedding and that resides on a flat torus for which the sides are axis-aligned. Testing and constructing the rectangular dual, if applicable, can be done efficiently. xxx \Issue 00000 \HeadingTitle Rectangular Duals on the Cylinder and the Torus \HeadingAuthor T. Biedl, P. Kindermann, and J. Klawitter \authorOrcid [first]Therese Biedl0000-0002-9003-3783 first]University of Waterloo, Canada \authorOrcid [second]Philipp Kindermann0000-0002-9003-3783 second]Universität Trier, Germany \authorOrcid [third]Jonathan Klawitter0000-0001-8917-5269 third]University of Auckland, Aotearoa New Zealand \Ack Jonathan Klawitter was supported by the Beyond Prediction Data Science Research Programme (MBIE grant UOAX1932). Therese Biedl is supported by NSERC, FRN RGPIN-2020-03958. Figure 1 : A rectangular dual on the cylinder and on the torus. 1 Introduction In a contact representation \mathcal{R} of a graph G each vertex w of G is mapped to an object \mathcal{R}(w) such that two vertices u and v are adjacent in G if and only if \mathcal{R}(u) and \mathcal{R}(v) touch, that is, they intersect with disjoint interiors; all other objects are disjoint. A famous example are Koebe’s coin graphs [ 31 ] , which can represent all planar graphs. Further examples include contact graphs of triangles [ 17 , 42 ] , squares and rectangles [ 8 , 30 , 16 ] , line segments and arcs [ 27 , 1 ] , and unit disks [ 28 , 20 ] . A rectangular dual of a plane graph G is a commonly studied type of contact representation where each vertex v is mapped to a non-empty, axis-aligned rectangle satisfying two conditions (see Fig. 2 ): (i) No four rectangles share a point; (ii) the union of the rectangles is a rectangle. It has been characterized repeatedly when a plane graph G admits a rectangular dual [ 26 , 35 , 32 , 45 , 46 , 34 ] , and how to test these conditions and construct the rectangular dual in linear time [ 4 , 29 , 6 , 34 ] . Rectangular duals have originally been studied due to their relation to floor plans in architecture [ 40 ] and VLSI design [ 37 , 47 ] , and to rectangular cartograms from cartography [ 24 , 39 ] . Here we are interested in generalizing rectangular duals from the plane to other surfaces, specifically, to the cylinder and the torus as shown in Fig. 1 . A common way to represent the surface of the cylinder [torus] is with a parallelogram Q , called the fundamental or canonical polygon , where one pair [both pairs] of opposite sides of Q are identified; imagine cutting the cylinder [torus] along a path [two cycles] and then mapping the surface onto Q . We also speak of Q as the flat cylinder or flat torus , accordingly. If Q has axis-parallel sides, we call it the rectangular flat cylinder/torus ; otherwise, we call it slanted . We assume that we have a standing cylinder and thus call the identified sides of a flat cylinder Q the left and right side. A cylindrical [ toroidal ] graph G is a graph embedded on the cylinder [torus] such that no two edges cross. Note that while a planar triangulated graph has a unique embedding in the plane (up to the choice of the outer face), this is not the case for a toroidal triangulated graph: Given one embedding, we can obtain another one by, roughly speaking, cutting the torus along a cycle through the hole (or around the body), twisting it and glueing it back together; this operation is known as a Dehn twist . Hence, when working with a toroidal graph we may also need a combinatorial description of how the graph is embedded on the flat torus (defined in Section 2 ). For rectangular duals of cylindrical and toroidal graphs, we consider representations on a fundamental polygon Q that maintain the characteristic properties of planar rectangular duals. In particular, we assume that no four rectangles share a point. Similar to how a planar rectangular dual is bounded by four axis-aligned line segments, we want both the top and bottom of a cylindrical rectangular dual to be bounded by a horizontal line. On the torus on the other hand, we have no border and thus require the rectangular dual to fully cover Q . See Figs. 1 , 2 and 3 for examples and Section 2 for precise definitions. Since rectangles may extend across an (identified) side of the fundamental polygon, we can, unlike in the case of planar rectangular duals, realize separating triangles (i.e. a triangle that is not the boundary of a face), or also loops or parallel edges. (a) Plane rectangular dual (b) Cylindrical rectangular dual (c) Toroidal rectangular dual Figure 2 : Rectangular duals on different surfaces. An important notion when working with a rectangular dual is a regular edge labeling (REL) , which, roughly speaking, is a 2-coloring and orientation of the edges that combinatorially describe how rectangles touch (see Section 2 for details). Introduced by He [ 26 ] , a REL can be found (if one exists) for planar graphs and used to construct rectangular duals in linear time [ 29 ] ; any rectangular dual naturally gives rise to a REL. In addition, RELs are fundamental tool in a variety of related applications, such as area-universality, constrained drawings, simultaneous and partial representation extensions, and morphing [ 29 , 23 , 21 , 13 , 14 ] . Bernard, Fusy, and Liang [ 3 ] generalized Schnyder woods and REL as well as other combinatorial structures of planar graphs to Grand Schnyder woods. Bonichon and Lévêque [ 7 ] studied toroidal RELs, yet did not explore RELs as a tool to construct toroidal rectangular duals. This and also the recent work on visibility representations on the torus and Klein bottle [ 5 ] , motivated this work. Contribution. In this paper, we characterize exactly when a cylindrical graph (with fixed embedding) has a rectangular dual on the flat cylinder. For toroidal graphs, a similar characterization remains open, but we provide a significant and non-trivial step by arguing when a given REL can be realized as a rectangular dual. More precisely, given a toroidal graph G , a REL \mathcal{L} , and an embedding on a flat torus, we can decide in linear time whether G has a rectangular dual \mathcal{R} on a flat torus that realizes \mathcal{L} , i.e. the REL that arises from \mathcal{R} is