A d-dimensional box (or d-box) is a set \([a_1,b_1]\times \cdots \times [a_d,b_d]\) where \([a_i,b_i]\) , for \(i \in [d]\) , are closed intervals on the real line. A d-dimensional cube (or d-cube) is a d-box with the constraint \(b_i-a_i=1\) for each \(i \in [d]\) . The boxicity (cubicity) of a graph G is the minimum integer d such that there exists a function that maps every vertex of G to a d-box (or d-cube respectively) so that two distinct vertices of G have an edge in G if and only if their corresponding d-boxes intersect. We survey some key results on the boxicity and cubicity of graphs, including bounds, general techniques, computational hardness results, and relationship with other graph invariants.
