Algunas preguntas sobre gráficos toroidales

Question

El grafo completo $K_4$ es planar, y al igual que todo grafo planar, también es incrustable en el toro.

a) ¿Por qué $K_4$ cuenta como una triangulación de la esfera, pero no del toro?

b) ¿Cuál es el nombre de los grafos que son toroidales, pero no planares?

c) ¿Existe algún criterio para grafos toroidales comparable a los teoremas de Kuratowski para grafos planares?

Answer 1

Quieres el libro Topological Graph Theory de Gross y Tucker.

Nota que $K_7$ puede ser incrustado en el toro, página 137. Así que, mi suposición para la parte (a) es que no puedes dibujar $K_4$ en el toro de tal manera que cada tripleta de aristas formando un triángulo en el grafo realmente limite una región simplemente conexa en la superficie.

(b) llamado género uno.

(c) no estoy seguro. Nota que los completos bipartitos $K_{4,4}$ y $K_{3,6}$ son de género uno, página 211, Teorema 4.5.3, Ringel (1965)

Answer 2

Una incrustación es triangular si cada cara es un triángulo. Para la incrustación de $ K_4 $ que tienes en mente, una cara no está limitada por un triángulo, la cara "exterior".

Nota que para superficies distintas a la esfera, se requiere que cada cara sea homeomorfa a un disco, es decir, la incrustación debe ser celular. Los grafos con incrustaciones celulares en una superficie dada forman una clase menor cerrada, por lo que según el teorema de Robertson-Seymour existe una clase finita de menores prohibidos y por lo tanto tenemos un buen análogo del teorema de Kuratowski. Sin embargo, nota que finito no significa pequeño.