"Planar" gráficos de Möbius en tiras

Question

Hay una manera fácil de saber si un gráfico que puede ser incrustado en una cinta de Moebius (sin bordes cruce)?

Una versión específica de este: si un gráfico simple con un número impar de vértices tiene todos los vértices de grado 4, puede ser incrustado en una cinta de Moebius?

---

Respuesta de resumen:

• Hay 103 prohibido subdiagramas de la cinta de Moebius que son explícitamente conocida y dibujado en la página 212ff de Dan Arcediano de la tesis.
• Hay 35 prohibido a menores de edad para la cinta de Moebius, que son explícitamente conocido, y, aún mejor, sólo hay 6 cúbicos prohibido a los menores de edad, cada uno con una explicación intuitiva.

Todavía no he contestado a la segunda pregunta, pero Jim Belk excelente explicación me ha dado buenas ideas.

Answer 1

Aquí está la respuesta por Jim Belk:

Hay 35 diferentes prohibido a menores de edad para el plano proyectivo, y estos han sido calculados de forma explícita. (Ver Mohar y Thomassen, pg. 198 para la lista completa).

Este es un plano proyectivo. Si un gráfico que puede ser incrustado en el plano proyectivo, entonces solo perfore un agujero en el avión en algún momento usted no está utilizando la incrustación, y usted tiene una incrustación en la banda de Möbius. Y si puede ser integrado en la banda de Möbius, que puede ser incrustado en el plano proyectivo desde la banda de Möbius es un subconjunto del plano proyectivo.

En un sentido tal vez esto no es totalmente responder a la pregunta. Para planaridad, es necesario que la característica de Euler ser de 2. Es eso suficiente? Si es así, tendría que tener un criterio que no se mencionan explícitamente cómo muchos prohibido a los menores de edad no son, o que los gráficos son.

Answer 2

Como anon notas en un comentario, para esta pregunta, la cinta de Moebius es el mismo que el plano proyectivo. No hay duda de que usted está familiarizado con el teorema de Kuratowski para incrustar en una esfera. Para cada superficie, hay un teorema análogo, es decir, una lista limitada de un mínimo de no-integrable gráficos. Se ha encontrado que estas listas, aunque finito, son mucho más grandes para otras superficies que son de la esfera, y sólo muy pocos de estas listas han sido encontrados. Creo que el plano proyectivo puede ser uno de los navegadores para los que la lista es conocida, pero grande, tan grande que el uso de la misma para determinar embedability no es fácil (al menos, no con la mano).

Soy consciente de que hay eficiente de la planaridad de los algoritmos, que no se basan directamente en Kuratowski. No sé si hay algoritmos similares para la proyectiva del plano (o en otras superficies).

EDIT: he encontrado una referencia a una lista de 103 gráficos que hacen de la cinta de Moebius (equivalentemente, proyectiva del plano) lo $K_5$ $K_{3,3}$ do para el avión (lo que es equivalente, de la esfera).