Incorporation d'un graphique en tant que collection de tétraèdres intérieurs disjoints

Définissez un maillage en 3D comme une collection connectée de tétraèdres aux intérieurs disjoints (donc les tétraèdres ne partagent que k-faces, ). Étant donné un graphe arbitraire, existe-t-il une procédure efficace pour tester s'il peut être incorporé en tant que maillage?$k \le 2$

Ici, une incorporation est un mappage des sommets du graphique aux points dans et des arêtes aux lignes droites de sorte que les arêtes ne se coupent qu'aux sommets, et les faces ne se coupent qu'aux bords, et aucune face ne se croise à l'intérieur.$R^3$

$\mathbb{R}^d$$\mbox{EMBED}_{3\rightarrow3}$

EDIT: mise à jour. En fait, ma réponse s'applique aux plongements PL. Pour les plongements linéaires, le problème est connu pour être dans PSPACE. Je ne sais pas si quelque chose d'autre est connu.