Incrustar un gráfico como una colección de tetraedros disjuntos en el interior

Defina una malla en 3D como una colección conectada de tetraedros con interiores disjuntos (para que los tetraedros solo compartan caras , ). Dado un gráfico arbitrario, ¿existe un procedimiento eficiente para probar si se puede incrustar como una malla? $k \le 2$

Aquí, una incrustación es un mapeo de vértices del gráfico a puntos en y bordes a líneas rectas de manera que los bordes solo se cruzan en los vértices, y las caras solo se cruzan en los bordes, y no hay dos caras que se crucen en su interior. $R^3$

ds.algorithms graph-theory Suresh Venkat
fuente

¿Te refieres a líneas o segmentos de línea? Aclare los dos tipos de bordes: las caras están en el tetraedro y los bordes que ha mencionado están en el gráfico ... También necesita que todos los bordes tetraédricos sean bordes de gráfico, o simplemente incrustaré cualquier gráfico en el gráfico completo Obtengo puntos en la curva de momento.

Jack

Me refiero a segmentos de línea, y sí, todos los bordes tetraédricos son bordes de gráfico. No estoy seguro de entender lo que quieres decir con 'dos tipos' de bordes.

Suresh Venkat

G

$G$

G

$G$

@ Jɛ ﬀ E Creo que, según la fuente de la pregunta, la interpretación correcta de la pregunta debería ser "¿Es G el esqueleto 1 de una malla?". Pero también me interesaría el caso cuando G es un subgrafo del esqueleto 1. Por lo tanto, las caras de dimensiones superiores no son parte de G, pero el requisito de que la incrustación sea una malla válida limita a G. Espero que esto tenga sentido.

Suresh Venkat

Incrustar un gráfico como una colección de tetraedros disjuntos en el interior

Respuestas: