<p>See "Squarability of rectangle arrangements", Konečný, Kučera, Opler, Sosnovec, Šimsa, and Töpfer, <a href="http://www.sfu.ca/~shermer/CCCG2016/" rel="nofollow">CCCG 2016</a>. In particular their Theorem 6 proves for all $d$ the existence of graphs with boxicity 2 and cubicity $d$.</p>

CC BY-SA 3.0
2016-08-05T00:32:59.553Z
2016-08-05T00:32:59.553Z
David Eppstein
<p>Is it known if the class of intersection graphs of rectangles is equal to the class of intersection graphs of squares (not necessarily unit)?</p>

CC BY-SA 3.0
2016-08-03T04:24:21.687Z
Can you draw $K_{3,3}$ with squares? It can be drawn as 3 horizontal and 3 vertical rectangles.
Andrew Morgan
CC BY-SA 3.0
2016-08-03T07:09:49.240Z
Are the squares and rectangles axis-aligned or can they have arbitrary orientations?
David Eppstein
CC BY-SA 3.0
2016-08-03T14:52:45.753Z
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
CC BY-SA 3.0
2016-08-03T14:56:53.967Z
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
CC BY-SA 3.0
2016-08-03T16:39:11.790Z
According to https://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
CC BY-SA 3.0
2016-08-20T07:54:37.883Z
@Jim Nastos: It seems to me that every tree should have cubicity 2. This can be proved inductively for rooted trees, where the induction is on the height of the tree. Such a tree can be represented as the intersection graph of squares, so that the root is the unique northern-most square. In the inductive step, take a huge northern-most square for the new root, and put the representations for the subtrees rooted at children just below it.
Gamow
<graph-theory><computational-geometry>
Intersection graphs of squares and rectangles
JS_
# Intersection graphs of squares and rectangles

(Asked by: username_0 on 2016-08-03)

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

**Tags:** graph-theory, computational-geometry
> **Comments:**
> **username_1**: Can you draw $K_{3,3}$ with squares? It can be drawn as 3 horizontal and 3 vertical rectangles.  
> **username_2**: Are the squares and rectangles axis-aligned or can they have arbitrary orientations?  
> **username_1**: 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.  
> **username_1**: 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.  
> **username_3**: According to https://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.  
> **username_4**: @Jim Nastos: It seems to me that every tree should have cubicity 2. This can be proved inductively for rooted trees, where the induction is on the height of the tree. Such a tree can be represented as the intersection graph of squares, so that the root is the unique northern-most square. In the inductive step, take a huge northern-most square for the new root, and put the representations for the subtrees rooted at children just below it.  

---

## 1 answers

### Answer by username_2 on 2016-08-05. Score: 2 | Accepted answer

See "Squarability of rectangle arrangements", Konečný, Kučera, Opler, Sosnovec, Šimsa, and Töpfer, [CCCG 2016](http://www.sfu.ca/~shermer/CCCG2016/). In particular their Theorem 6 proves for all $d$ the existence of graphs with boxicity 2 and cubicity $d$.


---

