En la teoría de grafos topológicos , el teorema de Hanani-Tutte es el resultado de la paridad de los cruces de bordes en un dibujo de grafos . Establece que cada dibujo en el plano de un gráfico no plano contiene un par de bordes independientes (no ambos comparten un punto final) que se cruzan un número impar de veces. De manera equivalente, se puede expresar como un criterio de planaridad: un gráfico es plano si y solo si tiene un dibujo en el que cada par de bordes independientes se cruza uniformemente (o no se cruza en absoluto). [1]
Historia
El resultado lleva el nombre de Haim Hanani , quien demostró en 1934 que cada dibujo de las dos gráficas mínimas no planas K 5 y K 3,3 tiene un par de aristas con un número impar de cruces, [2] y después de WT Tutte , quien declaró el teorema completo explícitamente en 1970. [3] Un desarrollo paralelo de ideas similares en topología algebraica se le ha atribuido a Egbert van Kampen , Arnold S. Shapiro y Wu Wenjun . [4] [5] [6] [7] [8] [9]
Aplicaciones
Una consecuencia del teorema es que probar si una gráfica es plana se puede formular como la resolución de un sistema de ecuaciones lineales sobre el campo finito de orden dos . Estas ecuaciones se pueden resolver en tiempo polinómico , pero los algoritmos resultantes son menos eficientes que otras pruebas de planaridad conocidas. [1]
Generalizaciones
Para otras superficies S además del plano, se puede dibujar un gráfico en S sin cruces si y solo si se puede dibujar de tal manera que todos los pares de aristas se crucen un número par de veces; esto se conoce como el teorema débil Hanani-Tutte de S . El fuerte teorema de Hanani-Tutte, conocido tanto por el plano proyectivo como por el plano euclidiano, establece que se puede dibujar una gráfica sin cruces en S si y solo si se puede dibujar de tal manera que todos los pares independientes de aristas se crucen un número par de veces, sin tener en cuenta el número de cruces entre bordes que comparten un punto final. [10]
El mismo enfoque, en el que se muestra que los pares de aristas con un número par de cruces pueden descartarse o eliminarse en algún tipo de dibujo gráfico y utiliza este hecho para establecer un sistema de ecuaciones lineales que describen la existencia de un dibujo, ha sido aplicado a varios otros problemas de dibujo de gráficos, incluidos dibujos planos hacia arriba , [11] dibujos que minimizan el número de bordes no cruzados, [12] [13] y planaridad agrupada . [14]
Referencias
- ^ a b Schaefer, Marcus (2013), "Hacia una teoría de la planaridad: Hanani-Tutte y variantes de planaridad", Journal of Graph Algorithms and Applications , 17 (4): 367–440, doi : 10.7155 / jgaa.00298 , MR 3094190.
- ^ Chojnacki, cap. (1934), "Über wesentlich unplättbare Kurven im dreidimensionalen Raume" , Fundamenta Mathematicae , Instituto de Matemáticas de la Academia Polaca de Ciencias, 23 (1): 135-142, doi : 10.4064 / fm-23-1-135-142. Ver en particular (1), p. 137.
- ^ Tutte, WT (1970), "Hacia una teoría del cruce de números", Journal of Combinatorial Theory , 8 : 45–53, doi : 10.1016 / s0021-9800 (70) 80007-2 , MR 0262110.
- ^ Levow, Roy B. (1972), "Sobre el enfoque algebraico de Tutte a la teoría de los números cruzados", Actas de la Tercera Conferencia Sureste sobre Combinatoria, Teoría de Gráficos y Computación (Florida Atlantic Univ., Boca Raton, Fla., 1972) , Florida Atlantic Univ., Boca Raton, Fla., Págs. 315–314, MR 0354426.
- ^ Schaefer, Marcus, "Hanani – Tutte y resultados relacionados", en Bárány, I .; Böröczky, KJ; Tóth, GF; et al. (eds.), Geometry — Intuitive, Discrete, and Convex — A Tribute to László Fejes Tóth (PDF) , Bolyai Society Mathematical Studies, Berlín: Springer
- ^ van Kampen, ER (1933), "Komplexe in euklidischen Räumen", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg , 9 (1): 72–78, doi : 10.1007 / BF02940628 , MR 3069580.
- ^ Wu, Wen-Tsün (1955), "Sobre la realización de complejos en espacios euclidianos. I", Acta Mathematica Sinica , 5 : 505–552, MR 0076334.
- ^ Shapiro, Arnold (1957), "Obstrucciones para la incrustación de un complejo en un espacio euclidiano. I. La primera obstrucción", Annals of Mathematics , Second Series, 66 (2): 256-269, doi : 10.2307 / 1969998 , JSTOR 1969998 , MR 0089410.
- ^ Wu, Wen Jun (1985), "Sobre la incrustación plana de gráficos lineales. I", Journal of Systems Science and Mathematical Sciences , 5 (4): 290-302, MR 0818118. Continuado en 6 (1): 23–35, 1986 .
- ^ Pelsmajer, Michael J .; Schaefer, Marcus; Stasi, Despina (2009), "Strong Hanani-Tutte en el plano proyectivo", SIAM Journal on Discrete Mathematics , 23 (3): 1317-1323, CiteSeerX 10.1.1.217.7182 , doi : 10.1137 / 08072485X , MR 2538654.
- ^ Fulek, Radoslav; Pelsmajer, Michael J .; Schaefer, Marcus; Štefanković, Daniel (2013), "Hanani – Tutte, monotone drawings, and level-planarity", en Pach, János (ed.), Treinta ensayos sobre teoría de grafos geométricos , Springer, ISBN 978-1-4614-0110-0.
- ^ Pach, János ; Tóth, Géza (2000), "¿Qué número de cruce es de todos modos?", Journal of Combinatorial Theory , Serie B, 80 (2): 225–246, doi : 10.1006 / jctb.2000.1978 , MR 1794693.
- ^ Pelsmajer, Michael J .; Schaefer, Marcus; Štefankovič, Daniel (2007), "Eliminación de cruces pares", Journal of Combinatorial Theory , Serie B, 97 (4): 489–500, doi : 10.1016 / j.jctb.2006.08.001 , MR 2325793.
- ^ Gutwenger, C .; Mutzel, P .; Schaefer, M., "Experiencia práctica con Hanani – Tutte para probar c -planarity", Actas de 2014 del Decimosexto Taller sobre Ingeniería de Algoritmos y Experimentos (ALENEX) , págs. 86–97, doi : 10.1137 / 1.9781611973198.9.