Is every countable graph spatial? I know that not every finite graph is planar. And I know that every finite graph can be drawn in $\mathbb R^3$ without edge crossings. What about countably infinite graphs?
 A: You can even use straight lines as edges.
The line segments $AB$ and $CD$ can only intersect if $A,B,C,D$ are coplanar. Pick $A_1,A_2, \ldots$ recursively as follows: If youhave already picked $A_1,\ldots,A_{n-1}$ so that no four are coplanar and (no three collinear), consider the ${n\choose 3}$ planes defined by them. Finitely many planes cannot cover $\mathbb R^3$, so we can pick $A_n$ such that it is on none of thes planes, hence we have still avoided four coplanar points. Ultimately this gives countably many points $\{\,A_n\mid n\in\mathbb N\,\}$ such that no two straight line segments among these vertices intersect.

Now let's do an explicit construction with continuum many vertices:
Four points $(x_i,y_i,z_i)$ are coplanar iff
$$\tag1 \det\begin{pmatrix}1&1&1&1\\
x_1&x_2&x_3&x_4\\
y_1&y_2&y_3&y_4\\
z_1&z_2&z_3&z_4\\
\end{pmatrix}=0.$$
Then if we let $A_t=(t,t^2,t^3)$, the uncountably many points $\{\,A_t\mid t\in\mathbb R\,\}$ have the property that not two line segments between them intersect! This follows from $(1)$ because a polynomial of degree $\le 3$ is uniquely determined by its values at four points.
A: Yes, it can be embedded in $\Bbb R^3$. The point is that when you try to embed, you can do this by avoiding self-intersections by a small perturbation (the same cannot be done in $\Bbb R^2$). This holds also for locally infinite (but countable) graphs.
A: Here is an 'explicit' (if ugly) construction:
Let $\phi: \mathbb{Z}^2 \to \mathbb{Z}$ be a bijection, and
suppose the vertices are a subset of $\mathbb{Z}$ and the vertices a subset of $ \mathbb{Z}^2$.
Then map a vertex $v \in \mathbb{Z}$ to $(v,0,0) \in \mathbb{R}^3$, and map an edge $(h,t) \in \mathbb{Z}^2$ to the path $(h,0,0) \to (h,1, \phi(h,t)) \to (t,1,\phi(h,t)) \to (t, 0,0)$.
It is straightforward to verify that two edges $(h,t),(h',t')$ cross iff $\phi(h,t)=\phi(h',t')$ iff $h=h'$ and $t=t'$.
Note: The above construction can be easily extended to any set of vertices $V$ and edges $E$ for which there are injective functions $\nu:V \to \mathbb{R}$ and $\phi:E \to \mathbb{R}$.
