# Intersection graphs of squares and rectangles

Is it known if the class of intersection graphs of rectangles is equal to the class of intersection graphs of squares (not necessarily unit)?

• Can you draw $K_{3,3}$ with squares? It can be drawn as 3 horizontal and 3 vertical rectangles. – Andrew Morgan Aug 3 '16 at 4:24
• Are the squares and rectangles axis-aligned or can they have arbitrary orientations? – David Eppstein Aug 3 '16 at 7:09
• If the squares must be axis-aligned, here is a strategy to prove that $K_{3,3}$ can't be drawn: (i) show (using convexity of squares) that there is essentially only one way to draw $C_4$ with squares; (ii) use (i) to show that any drawing of $K_{3,3}$ requires putting two squares inside a $C_4$ ring so that one square touches only the top and bottom of the ring, and the other square touches only the left and right squares of the ring; (iii) conclude that this is impossible, as it requires the rectangle inside the ring to be both wider than it is tall and taller than it is wide. – Andrew Morgan Aug 3 '16 at 14:52
• However, this can't work if the squares are allowed to have arbitrary orientations, or even if they're just allowed to be half-turned, because you can draw $K_{3,3}$ as the intersection graph of some squares this way. The basic idea of the construction is to make a 4-cycle that's shaped like a trapezoid in which the top edge is very short and the bottom edge is very long. You can then put in a small-ish square near the top that connects both side squares without touching the top or bottom, and then put in a 45-degree-rotated square that connects the top and bottom without touching the sides. – Andrew Morgan Aug 3 '16 at 14:56
• According to arxiv.org/pdf/1603.09570v1.pdf , all trees have boxicity 2 but not cubicity 2, and the complexity to determine the cubicity of trees is unknown. But their citation of this result refers to another arxiv manuscript. – JimN Aug 3 '16 at 16:39

See "Squarability of rectangle arrangements", Konečný, Kučera, Opler, Sosnovec, Šimsa, and Töpfer, CCCG 2016. In particular their Theorem 6 proves for all $d$ the existence of graphs with boxicity 2 and cubicity $d$.