Cubicity, Degeneracy, and Crossing Number

Abhijin Adiga, L. Sunil Chandran & Rogers Mathew
A k-box B=(R1,R2,...,Rk), where each Ri is a closed interval on the real line, is defined to be the Cartesian product R1 X R2 X ... X Rk. If each Ri is a unit length interval, we call B a k-cube. Boxicity of a graph G, denoted as box(G), is the minimum integer k such that G is an intersection graph of k-boxes. Similarly, the cubicity of G, denoted as cub(G), is the minimum integer...