A k-box B = (R1, R k), where each R i is a closed interval on the real line, is defined to be the Cartesian product R1 × R2 × ⋯ × R k. If each R i is a unit-length interval, we call B a k-cube. The 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 k such that G is an intersection graph of k-cubes.It was shown in [L. Sunil Chandran, Mathew C. Francis, Naveen Sivadasan. Cubicity and bandwidth. Graphs and Combinatorics 29 (1) (2013) 45-69] that, for a graph G with n vertices and maximum degree δ, cub (G) ≤ ⌈ 4 (δ + 1) log n ⌉ In this paper we show the following: •For a k-degenerate graph G, cub (G) ≤ (k + 2) ⌈ 2e log n ⌉ This bound is tight up to a constant factor. Since k is at most δ and can be much lower, this clearly is an asymptotically stronger result. Moreover, we have an efficient deterministic algorithm that runs in O (n2k) time to output an O (k log n) -dimensional cube representation for G. The above result has the following interesting consequences:•If the crossing number of a graph G is t, then box (G) is O(t14⌈logt⌉34). This bound is tight up to a factor of O((logt)14). We also show that if G has n vertices, then cub (G) is O ( log n + t1 / 4 log t) •Let dim(P) denote the poset dimension of a partially ordered set (P,≤). We show that dim(P)≤2(k+2)⌈2elogn⌉, where k denotes the degeneracy of the underlying comparability graph of P.•We show that the cubicity of almost all graphs in the G(n,m) model is O(davlogn), where dav=2mn denotes the average degree of the graph under consideration. © 2013 Elsevier Ltd.