Paper detail

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$. In the first part of this note, we prove that every graph on $m$ edges has boxicity $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ère 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ère invariant of $G$, denoted by $μ(G)$. We observe that every graph $G$ has boxicity $O(μ(G)^4(\log μ(G))^2)$, while there are graphs $G$ with boxicity $Ω(μ(G)\sqrt{\log μ(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 $Ω(\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.