2.00 p.m.
Cubicity, Degeneracy and Crossing Number
Rogers Mathew
IISc, Bangalore.
28-06-11

---

Abstract

A k-box B=(R_1,R_2,...,R_k), where each R_i is a closed interval on the real line, is defined to be the Cartesian product R_1 x R_2 x ... x 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 by Chandran et al. that, for a graph G with maximum degree D, cub(G) <= \lceil 4(D +1) log n \rceil. In this talk, we show that, for a k-degenerate graph G, cub(G) <= (k+2) \lceil 2e log n \rceil. Since k is at most D and can be much lower, this clearly is a stronger result. We also give an efficient deterministic algorithm that runs in O(n^2k) time to output a 8k(\lceil 2.42 \log n\rceil + 1) dimensional cube representation for G.

The crossing number of a graph G, denoted as CR(G), is the minimum number of crossing pairs of edges, over all drawings of G in the plane. An important consequence of the above result is that if the crossing number of a graph G is t, then box(G) is O(t^{1/4} {\lceil\log t\rceil}^{3/4}). This bound is tight upto a factor of O((\log t)^{\frac{3}{4}}).