2025/06/08 by Thérèse Biedl, Philipp Kindermann, Biedl, Therese +3
Computer Science · Mathematics · #05C62 #68R10 #Advanced Combinatorial Mathematics #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Geometric and Algebraic Topology
paper · pdf · doi:10.48550/arxiv.2506.07170
openalex publication_date 2025/06/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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.