Defina uma malha em 3D como uma coleção conectada de tetraedros com interiores separados (para que os tetraedros compartilhem apenas k-faces, ). Dado um gráfico arbitrário, existe um procedimento eficiente para testar se ele pode ser incorporado como uma malha?
Aqui, uma incorporação é um mapeamento de vértices do gráfico para pontos em e arestas para linhas retas, de modo que as arestas se cruzem apenas nos vértices e as faces se cruzem apenas nas arestas, e não haja duas faces no interior.
ds.algorithms
graph-theory
Suresh Venkat
fonte
fonte
Respostas:
Na dureza de incorporar complexos simples emRd , afirma-se que é pelo menos tão difícil quanto reconhecer uma 3-esfera, que se sabe estar em NP, mas não se sabe que esteja em P. Eles continuam dizendo que, pelo que sabemos, o problema pode ser indecidível.EMBED3→3
EDIT: Atualização. Na verdade, minha resposta se aplica a casamentos em PL. Para incorporações lineares, sabe-se que o problema está no PSPACE. Não sei se mais alguma coisa é conhecida.
fonte