Встраивание графа как совокупности внутренних непересекающихся тетраэдров

9

Определите сетку в 3D как связанную совокупность тетраэдров с непересекающимися внутренностями (поэтому тетраэдры имеют только k-грани, К2). Учитывая произвольный граф, есть ли эффективная процедура для проверки, если он может быть встроен в виде сетки?

Здесь вложение - это отображение вершин графа в точках в а ребер - в прямые линии, так что ребра пересекаются только в вершинах, а грани только пересекаются в ребрах, и никакие две грани не пересекаются в их внутренней части.р3

Суреш Венкат
источник
Вы имеете в виду линии или отрезки? Уточните, пожалуйста, два типа ребер: грани находятся в тетраэдрах, а ребра, о которых вы упомянули, находятся в графе ... Вам также нужно, чтобы все ребра тетраэдра были ребрами графа, или я просто вставлю любой граф в полный граф Я получаю из точек на момент кривой.
Джек,
Я имею в виду отрезки, и да, все тетраэдрические ребра являются ребрами графа. Я не уверен, что понимаю, что вы подразумеваете под «двумя типами» ребер.
Суреш Венкат
Вы имеете в виду "Есть г 1-скелет сетки? »или« Есть гподграф 1-скелета сетки? "или что-то еще? Откуда берутся многомерные лица?
Джеффс
@ Jɛ ff E Я думаю, что, исходя из источника вопроса, правильное отображение вопроса должно звучать так: «Является ли G 1-каркасом сетки». Но мне также будет интересен случай, когда G является подграфом 1-скелета. Таким образом, многомерные грани не являются частью G, но требование, чтобы вложение было допустимой сеткой, ограничивает G. Я надеюсь, что это имеет смысл.
Суреш Венкат

Ответы:

4

В твердости вложения симплициальных комплексов врd заявлено, что ССЫЛКА33 по крайней мере так же трудно, как распознать 3-сферу, которая, как известно, находится в NP, но неизвестна в P. Они продолжают утверждать, что, насколько нам известно, проблема может быть неразрешимой.

РЕДАКТИРОВАТЬ: Обновление. На самом деле мой ответ относится к вложениям PL. Известно, что для линейных вложений задача находится в PSPACE. Я не знаю, известно ли что-нибудь еще.

Шон Харкер
источник
1
Ах, хорошая ссылка. Я должен разобраться в этом немного более тщательно, поскольку их представление о PL-вложениях может быть немного слабее, чем то, что я хочу (это то, что они называют «линейным» вложением.
Суреш Венкат,
А ну понятно. Я не уловил этот нюанс. Штопать. Что ж, надеюсь, это будет полезно в любом случае :)
Шон Харкер