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.

  • $\begingroup$ 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. $\endgroup$
    – Jack
    May 29, 2011 at 6:49
  • $\begingroup$ 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. $\endgroup$ May 29, 2011 at 7:37
  • $\begingroup$ 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? $\endgroup$
    – Jeffε
    May 29, 2011 at 19:51
  • $\begingroup$ @JɛffE 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. $\endgroup$ May 29, 2011 at 20:13

1 Answer 1


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.

  • 1
    $\begingroup$ Ah, good reference. I have to puzzle through it a little more carefully since their notion of PL-embeddings might be a little weaker than the notion I want (which is what they call a 'linear' embedding. $\endgroup$ May 28, 2011 at 20:45
  • $\begingroup$ Oh, I see. I didn't catch that nuance. Darn. Well, hope it's helpful anyway :) $\endgroup$ May 28, 2011 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.