| Autor: |
Matěj Konečný, Kučera, S., Opler, M., Sosnovec, J., Šimsa, Š, Töpfer, M. |
| Rok vydání: |
2016 |
| Předmět: |
|
| Zdroj: |
Scopus-Elsevier |
| DOI: |
10.48550/arxiv.1611.07073 |
| Popis: |
We study when an arrangement of axis-aligned rectangles can be transformed into an arrangement of axis-aligned squares in $\mathbb{R}^2$ while preserving its structure. We found a counterexample to the conjecture of J. Klawitter, M. N\"ollenburg 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. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
