Rectangular Duals on the Cylinder and the Torus
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909642566664192 |
|---|---|
| author | Biedl, Therese Kindermann, Philipp Klawitter, Jonathan |
| author_facet | Biedl, Therese Kindermann, Philipp Klawitter, Jonathan |
| contents | A rectangular dual of a plane graph $G$ is a contact representation of $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 \textit{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_07170 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Rectangular Duals on the Cylinder and the Torus Biedl, Therese Kindermann, Philipp Klawitter, Jonathan Computational Geometry Discrete Mathematics 68R10, 05C62 A rectangular dual of a plane graph $G$ is a contact representation of $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 \textit{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. |
| title | Rectangular Duals on the Cylinder and the Torus |
| topic | Computational Geometry Discrete Mathematics 68R10, 05C62 |
| url | https://arxiv.org/abs/2506.07170 |