Boxicity and topological invariants

The boxicity of a graph $G=(V,E)$ is the smallest integer $k$ for which there exist $k$ interval graphs $G_i=(V,E_i)$, $1\le i\le k$, such that $E=E_1 \cap \cdots \cap E_k$\mathrm{.}Inthefirstpartofthisnote,weprovethateverygraphon$m$edgeshasboxicity$O(\sqrt{m \log m})$, which is asymptotically best possible. We use this result to study the connection between the boxicity of graphs and their Colin de Verdi`ere invariant, which share many similarities. Known results concerning the two parameters suggest that for any graph $G$, the boxicity of $G$ is at most the Colin de Verdi`ere invariant of $G$, denoted by $\mu (G)$. We observe that every graph $G$ has boxicity $O(\mu(G)^4(\log \mu(G))^2)$,whiletherearegraphs$G$withboxicity$\Omega(\mu(G)\sqrt{\log \mu(G)})$. In the second part of this note, we focus on graphs embeddable on a surface of Euler genus $g$. We prove that these graphs have boxicity $O(\sqrt{g}\log g)$, while some of these graphs have boxicity $\Omega(\sqrt{g \log g})$. This improves the previously best known upper and lower bounds. These results directly imply a nearly optimal bound on the dimension of the adjacency poset of graphs on surfaces.