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.

• Do you mean lines or line segments? Please clarify the two types of edges: faces are in the tetrahedra and the edges you've mentioned are in the graph... You also need that all tetrahedral edges are graph edges, or I'll just embed any graph in the complete graph I get from points on the moment curve. – Jack May 29 '11 at 6:49
• I mean line segments, and yes all tetrahedral edges are graph edges. I'm not sure I understand what you mean by 'two types' of edges. – Suresh Venkat May 29 '11 at 7:37
• Do you mean "Is $G$ the 1-skeleton of a mesh?" or "Is $G$ a subgraph of the 1-skeleton of a mesh?" or something else? Where do the higher-dimensional faces come from? – Jeffε May 29 '11 at 19:51
• @JɛﬀE I think that based on the source of the question, the correct rendering of the question should be "Is G the 1-skeleton of a mesh". But I'd also be interested in the case when G is a subgraph of the 1-skeleton. Thus, the higher-dimensional faces are not part of G, but the requirement that the embedding be a valid mesh constrains G. I hope this makes sense. – Suresh Venkat May 29 '11 at 20:13

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.