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 '11 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$ – Suresh Venkat May 29 '11 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 '11 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$ – 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.

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.

| cite | improve this answer | |
  • 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$ – Suresh Venkat May 28 '11 at 20:45
  • $\begingroup$ Oh, I see. I didn't catch that nuance. Darn. Well, hope it's helpful anyway :) $\endgroup$ – Shaun Harker May 28 '11 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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