2015/09/02 by Jonathan Klawitter, Martin Nöllenburg, Klawitter, Jonathan +3 · 2 citations
Computer Science · Engineering · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Optimization and Packing Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1509.00835
openalex publication_date 2015/09/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider arrangements of axis-aligned rectangles in the plane. A geometric\narrangement specifies the coordinates of all rectangles, while a combinatorial\narrangement specifies only the respective intersection type in which each pair\nof rectangles intersects. First, we investigate combinatorial contact\narrangements, i.e., arrangements of interior-disjoint rectangles, with a\ntriangle-free intersection graph. We show that such rectangle arrangements are\nin bijection with the 4-orientations of an underlying planar multigraph and\nprove that there is a corresponding geometric rectangle contact arrangement.\nMoreover, we prove that every triangle-free planar graph is the contact graph\nof such an arrangement. Secondly, we introduce the question whether a given\nrectangle arrangement has a combinatorially equivalent square arrangement. In\naddition to some necessary conditions and counterexamples, we show that\nrectangle arrangements pierced by a horizontal line are squarable under certain\nsufficient conditions.\n