Embedding a graph as a collection of interior-disjoint tetrahedra Define a mesh in 3D as a connected collection of tetrahedra with disjoint interiors (so tetrahedra share only k-faces, $k \le 2$). Given an arbitrary graph, is there an efficient procedure to test if it can be embedded as a mesh ? 

Here, an embedding is a mapping of vertices of the graph to points in $R^3$ and edges to straight lines such that edges only intersect at vertices, and faces only intersect at edges, and no two faces intersect in their interior.
In Hardness of embedding simplicial complexes in $\mathbb{R}^d$ it is stated that $\mbox{EMBED}_{3\rightarrow3}$ is at least as hard as recognizing a 3-sphere, which is known to be in NP, but not known to be in P. They continue to say that for all we know, the problem may be undecidable.

EDIT: Update. Actually, my answer applies to PL embeddings. For linear embeddings the problem is known to be in PSPACE. I don't know if anything else is known.