Gráfico toroidal

En matemáticas , un gráfico toroidal es un gráfico que se puede incrustar en un toro . En otras palabras, los vértices del gráfico se pueden colocar en un toro de modo que no se crucen los bordes.

Un gráfico cúbico con 14 vértices incrustados en un toro.
El gráfico de Heawood y el mapa asociado incrustados en el toro.

Cualquier gráfico que se pueda incrustar en un plano también se puede incrustar en un toro. Un gráfico toroidal del género 1 se puede incrustar en un toro pero no en un plano. El gráfico de Heawood , el gráfico completo K 7 (y por lo tanto K 5 y K 6 ), el gráfico de Petersen (y por lo tanto el gráfico bipartito completo K 3,3 , ya que el gráfico de Petersen contiene una subdivisión del mismo), uno de los snarks de Blanuša , [1] y todas las escaleras de Möbius son toroidales. De manera más general, cualquier gráfico con cruce número 1 es toroidal. Algunas gráficas con números de cruce mayores también son toroidales: la gráfica de Möbius-Kantor , por ejemplo, tiene el número de cruce 4 y es toroidal. [2]

Cualquier gráfico toroidal tiene un número cromático como máximo 7. [3] El gráfico completo K 7 proporciona un ejemplo de gráfico toroidal con número cromático 7. [4]

Cualquier gráfico toroidal sin triángulos tiene un número cromático como máximo 4. [5]

Mediante un resultado análogo al teorema de Fáry , cualquier gráfico toroidal puede dibujarse con bordes rectos en un rectángulo con condiciones de contorno periódicas . [6] Además, en este caso se aplica el análogo del teorema del resorte de Tutte . [7] Los gráficos toroidales también tienen incrustaciones de libros con un máximo de 7 páginas. [8]

Por el teorema de Robertson-Seymour , existe un conjunto finito H de gráficos no toroidales mínimos, de tal manera que un gráfico es toroidal si y sólo si no tiene menor gráfica en H . Es decir, H forma el conjunto de menores prohibidos para los gráficos toroidales. No se conoce el conjunto completo H , pero tiene al menos 17 523 gráficos. Alternativamente, hay al menos 250,815 gráficos no toroidales que son mínimos en el orden topológico menor . Un gráfico es toroidal si y solo si no tiene ninguno de estos gráficos como topológico menor. [9]

  • El gráfico de Heawood y el mapa asociado incrustados en el toro.

  • El gráfico de Pappus y el mapa asociado incrustados en el toro.

    • Gráfico plano
    • Teoría de grafos topológicos
    • Poliedro Császár

    1. ^ Orbanić y col. (2004) .
    2. ^ Marušič y Pisanski (2000) .
    3. ^ Heawood (1890) .
    4. ^ Chartrand y Zhang (2008) .
    5. ^ Kronk y White (1972) .
    6. ^ Kocay, Neilson y Szypowski (2001) .
    7. ^ Gortler, Gotsman y Thurston (2006) .
    8. ^ Endo (1997) .
    9. ^ Myrvold y Woodcock (2018) .

    • Chartrand, Gary ; Zhang, Ping (2008), teoría de grafos cromáticos , CRC Press, ISBN 978-1-58488-800-0.
    • Endo, Toshiki (1997), "El número de páginas de las gráficas toroidales es como máximo siete", Discrete Mathematics , 175 (1-3): 87-96, doi : 10.1016 / S0012-365X (96) 00144-6 , MR  1475841.
    • Gortler, Steven J .; Gotsman, Craig; Thurston, Dylan (2006), "Discrete one-form on malhes and applications to 3D mesh parametrización" (PDF) , Computer Aided Geometric Design , 23 (2): 83–112, doi : 10.1016 / j.cagd.2005.05.002 , MR  2189438.
    • Heawood, PJ (1890), "Teoremas de coloración de mapas", Quarterly Journal of Mathematics , Primera serie, 24 : 322–339.
    • Kocay, W .; Neilson, D .; Szypowski, R. (2001), "Drawing graphs on the torus" (PDF) , Ars Combinatoria , 59 : 259–277, MR  1832459 , archivado desde el original (PDF) el 24 de diciembre de 2004 , consultado el 9 de septiembre de 2018 06.
    • Kronk, Hudson V .; White, Arthur T. (1972), "Un teorema de 4 colores para gráficos toroidales", Proceedings of the American Mathematical Society , American Mathematical Society, 34 (1): 83–86, doi : 10.2307 / 2037902 , JSTOR  2037902 , MR  0291019.
    • Marušič, Dragan ; Pisanski, Tomaž (2000), "El notable gráfico de Petersen generalizado G (8,3)" , Math. Eslovaca , 50 : 117–121[ enlace muerto permanente ] .
    • Myrvold, Wendy ; Woodcock, Jennifer (2018), "Un gran conjunto de obstrucciones toroidales y cómo se descubrieron", Electronic Journal of Combinatorics , 25 (1): P1.16, doi : 10.37236 / 3797
    • Neufeld, Eugene; Myrvold, Wendy (1997), "Pruebas prácticas de toroidalidad", Actas del octavo simposio anual ACM-SIAM sobre algoritmos discretos , págs. 574–580.
    • Orbanić, Alen; Pisanski, Tomaž ; Randić, Milán ; Servatius, Brigitte (2004), "Blanuša doble", Matemáticas. Comun. , 9 (1): 91–103.