Cubicity, degeneracy, and crossing number

A k-box B=(R1,…,Rk), where each Ri is a closed interval on the real line, is defined to be the Cartesian product R1×R2×⋯×Rk. If each Ri 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)logn⌉. In this paper we show the following:
- For a k-degenerate graph G, cub(G)≤(k+2)⌈2elogn⌉. 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(klogn)-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(logn+t1/4logt).
- 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.