Osadzanie wykresu jako zbioru czworościanów rozłącznych wewnętrznie

Zdefiniuj siatkę w 3D jako połączoną kolekcję czworościanów z rozłącznymi wnętrzami (więc czworościany mają tylko k-face, $k \le 2$). Czy na podstawie dowolnego wykresu istnieje skuteczna procedura sprawdzania, czy można go osadzić jako siatkę?

Osadzanie polega na odwzorowaniu wierzchołków wykresu na punkty w $R^3$ a krawędzie do linii prostych, tak że krawędzie przecinają się tylko w wierzchołkach, a ściany przecinają się tylko na krawędziach i żadne dwie ściany nie przecinają się w ich wnętrzu.

W Twardości osadzania prostych kompleksów w$\mathbb{R}^d$ Stwierdza się, że $\mbox{EMBED}_{3\rightarrow3}$ jest co najmniej tak trudne, jak rozpoznanie 3-kuli, o której wiadomo, że jest w NP, ale nie jest w P. Wciąż twierdzą, że z tego co wiemy, problem może być nierozstrzygalny.

EDYCJA: aktualizacja. Właściwie moja odpowiedź dotyczy osadzania PL. W przypadku osadzania liniowego problem występuje w PSPACE. Nie wiem czy coś jeszcze jest znane.