Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: 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\`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)$, while there are graphs $G$ with boxicity $\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.

4
The categories of this paper are: cond-mat
11
The categories of this paper are: hep-lat
32
The categories of this paper are: atom-ph
9
The categories of this paper are: nlin
21
The categories of this paper are: adap-org
10
The categories of this paper are: q-bio
34
The categories of this paper are: chem-ph
7
The categories of this paper are: hep-th
35
The categories of this paper are: mtrl-th
16
The categories of this paper are: stat
17
The categories of this paper are: q-fin
12
The categories of this paper are: nucl-th
14
The categories of this paper are: math-ph
24
The categories of this paper are: dg-ga
20
The categories of this paper are: acc-phys
1
The categories of this paper are: cs