  An axis-parallel $b$-dimensional box is a Cartesian product $R_1\times
R_2\times...\times R_b$ where $R_i$ is a closed interval of the form
$[a_i,b_i]$ on the real line. For a graph $G$, its \emph{boxicity} box(G) is
the minimum dimension $b$, such that $G$ is representable as the intersection
graph of boxes in $b$-dimensional space. Although boxicity was introduced in
1969 and studied extensively, there are no significant results on lower bounds
for boxicity. In this paper, we develop two general methods for deriving lower
bounds. Applying these methods we give several results, some of which are
listed below:
  (1) The boxicity of a graph on $n$ vertices with no universal vertices and
minimum degree $\delta$ is at least $n/2(n-\delta-1)$. (2) Consider the
$\mathcal{G}(n,p)$ model of random graphs. Let $ p \le 1- \frac{40 \log
n}{n^2}$. Then, for $G \in \mathcal{G}(n,p)$, almost surely
$box(G)=\Omega(np(1-p))$. On setting $p=1/2$ we immediately infer that almost
all graphs have boxicity $\Omega(n)$. (3) Spectral lower bounds for the
boxicity of $k$-regular graphs. (4) The boxicity of random $k$-regular graphs
on $n$ vertices (where $k$ is fixed) is $\Omega(k/\log k)$. (5) There exists a
positive constant$c$ such that almost all balanced bipartite graphs on $2n$
vertices with exactly $m$ edges have boxicity at least $c m/n$, for $ m\le c'
n^2/3$ for any positive constant $c' < 1$.
