  The 'separation dimension' of a graph $G$ is the smallest natural number $k$
for which the vertices of $G$ can be embedded in $\mathbb{R}^k$ such that any
pair of disjoint edges in $G$ can be separated by a hyperplane normal to one of
the axes. Equivalently, it is the smallest possible cardinality of a family
$\mathcal{F}$ of total orders of the vertices of $G$ such that for any two
disjoint edges of $G$, there exists at least one total order in $\mathcal{F}$
in which all the vertices in one edge precede those in the other. In general,
the maximum separation dimension of a graph on $n$ vertices is $\Theta(\log
n)$. In this article, we focus on bounded degree graphs and show that the
separation dimension of a graph with maximum degree $d$ is at most
$2^{9log^{\star} d} d$. We also demonstrate that the above bound is nearly
tight by showing that, for every $d$, almost all $d$-regular graphs have
separation dimension at least $\lceil d/2\rceil$.
