2016/11/21 by Matěj Konečný, Stanislav Kučera, Konečný, Matěj +9
Biochemistry, Genetics and Molecular Biology · Engineering · Mathematics · #Advanced Combinatorial Mathematics #Computational Geometry (cs.CG) #FOS: Computer and information sciences #Genome Rearrangement Algorithms #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1611.07073
openalex publication_date 2016/11/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study when an arrangement of axis-aligned rectangles can be transformed into an arrangement of axis-aligned squares in ℝ2 while preserving its structure. We found a counterexample to the conjecture of J. Klawitter, M. Nöllenburg and T. Ueckerdt whether all arrangements without crossing and side-piercing can be squared. Our counterexample also works in a more general case when we only need to preserve the intersection graph and we forbid side-piercing between squares. We also show counterexamples for transforming box arrangements into combinatorially equivalent hypercube arrangements. Finally, we introduce a linear program deciding whether an arrangement of rectangles can be squared in a more restrictive version where the order of all sides is preserved.