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

  • 4
    $\begingroup$ Can you draw $K_{3,3}$ with squares? It can be drawn as 3 horizontal and 3 vertical rectangles. $\endgroup$ Aug 3 '16 at 4:24
  • 6
    $\begingroup$ Are the squares and rectangles axis-aligned or can they have arbitrary orientations? $\endgroup$ Aug 3 '16 at 7:09
  • $\begingroup$ 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. $\endgroup$ Aug 3 '16 at 14:52
  • $\begingroup$ 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. $\endgroup$ Aug 3 '16 at 14:56
  • $\begingroup$ 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. $\endgroup$
    – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.