<p>In <a href="http://www.siam.org/proceedings/soda/2009/SODA09_093_matousekj.pdf" rel="nofollow">Hardness of embedding simplicial complexes in $\mathbb{R}^d$</a> 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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-05-28T20:45:48.030Z
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.
Suresh Venkat
CC BY-SA 3.0
2011-05-28T22:26:01.510Z
Oh, I see. I didn't catch that nuance. Darn. Well, hope it's helpful anyway :)
Shaun Harker
CC BY-SA 3.0
2011-05-28T16:49:17.417Z
2011-06-03T19:35:58.827Z
2011-06-03T19:35:58.827Z
Shaun Harker
<p>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 ? </p>

<p>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.</p>

CC BY-SA 3.0
2011-05-29T06:49:05.890Z
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
CC BY-SA 3.0
2011-05-29T07:37:38.337Z
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
CC BY-SA 3.0
2011-05-29T19:51:54.847Z
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ε
CC BY-SA 3.0
2011-05-29T20:13:17.203Z
@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
<ds.algorithms><graph-theory>
Embedding a graph as a collection of interior-disjoint tetrahedra
Suresh Venkat
# Embedding a graph as a collection of interior-disjoint tetrahedra

(Asked by: username_0 on 2011-05-27)

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.

**Tags:** ds.algorithms, graph-theory

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_2**: 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?  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_3 on 2011-05-28. Score: 4

In [Hardness of embedding simplicial complexes in $\mathbb{R}^d$](http://www.siam.org/proceedings/soda/2009/SODA09_093_matousekj.pdf) 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.

> **Comments:**
> **username_0**: 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.  
> **username_3**: Oh, I see. I didn't catch that nuance. Darn. Well, hope it's helpful anyway :)  

---

