Определите сетку в 3D как связанную совокупность тетраэдров с непересекающимися внутренностями (поэтому тетраэдры имеют только k-грани, ). Учитывая произвольный граф, есть ли эффективная процедура для проверки, если он может быть встроен в виде сетки?
Здесь вложение - это отображение вершин графа в точках в а ребер - в прямые линии, так что ребра пересекаются только в вершинах, а грани только пересекаются в ребрах, и никакие две грани не пересекаются в их внутренней части.
ds.algorithms
graph-theory
Суреш Венкат
источник
источник
Ответы:
В твердости вложения симплициальных комплексов врd заявлено, что ССЫЛКА3 → 3 по крайней мере так же трудно, как распознать 3-сферу, которая, как известно, находится в NP, но неизвестна в P. Они продолжают утверждать, что, насколько нам известно, проблема может быть неразрешимой.
РЕДАКТИРОВАТЬ: Обновление. На самом деле мой ответ относится к вложениям PL. Известно, что для линейных вложений задача находится в PSPACE. Я не знаю, известно ли что-нибудь еще.
источник