Hola usuario de nuestra página, descubrimos la solución a lo que necesitas, has scroll y la obtendrás aquí.
Solución:
(Creo que la pregunta de por qué los gráficos planos son excepcionales es importante. Se puede plantear no solo en el contexto de gráficos incrustables en otras superficies. Permítanme editar y elaborar, también tomando prestado de los comentarios).
Dualidad: Quizás la dualidad sea la propiedad crucial de los gráficos planos. Existe un teorema que afirma que el dual de una matroide gráfica M es una matroide gráfica si y solo si M es la matroide de un grafo plano. En este caso, el dual de M es la matroide del gráfico dual de G. (Ver este artículo de wikipedia). Esto significa que los circuitos de un gráfico plano están en correspondencia uno a uno con los cortes del gráfico dual.
Una manifestación importante de la singularidad de los gráficos planares (que creo que está relacionada con la dualidad) es la fórmula de Kasteleyn para el número de emparejamientos perfectos y la conexión con contar árboles.
Descripciones geométricas robustas: Otra diferencia conceptual es que los gráficos planos (3 conectados o máximos) son gráficos de politopos tridimensionales convexos y, por lo tanto, tienen propiedades geométricas adicionales que los gráficos sobre superficies no comparten.
La definición geométrica de gráficos planos (a diferencia de varias generalizaciones) es muy sólida. Un gráfico es plano si se puede dibujar en el plano de manera que las aristas no se crucen en sus interiores y estén representadas por curvas de Jordan; La clase de gráficos planos también es lo que obtenemos si reemplazamos “curvas de Jordan” por “intervalos de línea”, o si reemplazamos “sin intersección” por “número par de cruces”. El teorema de Koebe-Andreev-Thurston permite representar cada gráfico plano mediante el “gráfico en contacto” de círculos que no se superponen. Tanto las representaciones (relacionadas) mediante politopos convexos como mediante empaquetaduras circulares, pueden respetar el grupo de automorfismos del gráfico y su dual.
Construcciones inductivas simples. Otra propiedad excepcional de la clase de gráficos planos es que los gráficos planos se pueden construir mediante construcciones inductivas simples. (A este respecto, son similares a la clase de árboles, aunque las construcciones inductivas no son tan simples como las de los árboles). Esto falla para la mayoría de las generalizaciones de gráficos planos.
Una propiedad importante relacionada de los gráficos planos, los mapas y las triangulaciones (con vértices etiquetados) es que se pueden enumerar muy bien. Esta es la teoría de Tutte. (Tiene extensiones profundas a las superficies).
A menudo ocurre que los resultados sobre gráficos planos se extienden a otras clases. Como mencioné, la teoría de Tutte se extiende a triangulaciones de otras superficies. Otro ejemplo es el teorema fundamental del separador de Lipton-Tarjan, que se extiende a todos los gráficos con un menor prohibido.
El estudio de gráficas planas ha llevado a importantes conceptos teóricos de gráficas. Otra razón (de diferente naturaleza) por la que las gráficas planas son excepcionales es que varios conceptos importantes de la teoría de grafos se descubrieron al observar gráficas planas (o gráficas planas especiales). ) de la conjetura de cuatro colores sobre gráficas planas. De manera similar, los caminos y ciclos hamiltonianos se estudiaron primero para gráficos planos.
Gráficos sobre superficies y otras nociones que generalizan la planitud. Considerar la clase de todos los gráficos que se pueden incrustar en una superficie determinada es una extensión natural e importante de la planaridad. Pero, de hecho, para varias preguntas, los gráficos incrustables en superficies pueden no ser la generalización correcta de los gráficos planos.
David Eppstein mencionó otra generalización a través del invariante colin de Verdier. Esto describe una jerarquía de gráficos donde la siguiente clase después de los gráficos planos son “gráficos incrustables sin enlaces”. Esos son gráficos que se pueden incrustar en el espacio sin tener dos ciclos separados geométricamente enlazados. Al final resultó que esta es también una noción muy sólida y conduce a una hermosa clase de gráficos. (Todos tienen como máximo 4v-10 aristas donde v es el número de vértices; el caso conocido de la conjetura de Hadwiger para grafos que no tienen K_6 menor implica que todos son 5 coloreables). Otras clases en esta jerarquía siguen siendo muy misteriosas. Otras extensiones de planaridad son: 3) (no literalmente) Gráficos que no tienen K_r como menor; 4; 5) (Ambos muy problemáticos) Como mencionó Joe, gráficos de d-politopos, y también gráficos obtenidos de empaquetaduras de esferas en dimensiones superiores; 6) (no gráficos) complejos simpliciales r-dimensionales que no se pueden incrustar en dos veces la dimensión, 7) [A notion that I promoted over the years:] gráficos (y esqueleto) de d-polytope con un segundo número g (tórico) que desaparece, y muchos más.
Prohibidos menores y colorantes. En cuanto al segundo y tercer ítem de la pregunta. Acerca de la coloración, no estoy seguro de si deberíamos considerar las gráficas planas de 4 colores y las gráficas de coloración en otras superficies como fenómenos muy relacionados. Respecto a los menores prohibidos. El teorema de Kuratowski sobre superficies es un caso especial (y también un paso importante de la demostración) de un resultado mucho más general (la conjetura de Wagner probada por Robertson y Seymour) sobre cualquier clase menor de gráficos cerrados. Este resultado puede considerarse como una extensión del teorema de Kuratowski y también (y quizás más importante) que extiende el teorema de Kruskal y Nash-Williams en árboles. De hecho, el teorema de Kuratoski está muy relacionado con la imagen más general de la obstrucción topológica de la incrustabilidad. Si quisiera proponer una comprensión diferente (tal vez topológica) de la extensión del teorema de Kuratowski para superficies, entonces tal vez debería comenzar por el teorema del bien cuasi ordenamiento para árboles.
Como señala Gil Kalai, el teorema de Steinitz (un gráfico G es el gráfico de borde de vértice de un poliedro convexo tridimensional, si y solo si G es plano y está conectado en 3) es muy poderoso. Significa que las propiedades combinatorias (circuitos hamiltonianos, emparejamientos, etc.) de algo tridimensional se pueden estudiar observando un tipo especial de gráfico en 2 dimensiones. Nada completamente como esto sucede para los politopos convexos de dimensiones superiores. De manera similar, no sabemos cómo estudiar todos los “politopos toroidales” usando una clase especial de gráficos en el toro.
Lo que parece intrigante es la interfaz entre capturar propiedades “geométricas” de objetos a partir de propiedades combinatorias (teoría de grafos). Por ejemplo, desde hace algún tiempo me ha interesado saber qué poliedros convexos tridimensionales con todas sus caras triangulares se pueden realizar con triángulos isósceles como caras. Una forma de atacar esto es mirar las gráficas planas de 3 gráficas conectadas con al menos 4 vértices, todas cuyas caras son triángulos (gráficas planas máximas). Resulta que uno puede colorear los bordes de un gráfico de este tipo con dos colores ayb de modo que cada cara tenga dos bordes a y un borde b. Ahora uno puede preguntarse si estos colorantes se pueden realizar con triángulos isósceles congruentes, los colores ayb se utilizan para codificar las dos longitudes de los bordes de los triángulos isósceles congruentes. No es difícil demostrar que algunas gráficas planas máximas no se pueden realizar con triángulos isósceles congruentes, pero decir exactamente qué gráficas se pueden realizar de esta manera parece mucho más difícil. Además, la teoría de grafos me permitió ver muchas formas de realizar tales poliedros geométricamente, cuando tal realización es posible; en otras palabras, el mismo tipo combinatorio a menudo se puede realizar con triángulos isósceles congruentes de muchas maneras) distintas de las que tenía mucha simetría. Si 4 divide el número de caras de un gráfico plano máximo, uno puede colorear sus bordes con dos colores ayb de modo que el número de triángulos a, a, b y b, b, a sean iguales. Sin embargo, no he podido decir explícitamente cuándo tales coloraciones se traducen en realizaciones geométricas. Hablando libremente, las preguntas combinatorias parecen “fáciles” mientras que las geométricas parecen “difíciles”. No sé si los gráficos planos máximos con al menos 4 vértices se pueden realizar mediante poliedros convexos con triángulos isósceles. (Supongo que sí.) También hay preguntas interesantes cuando se permiten mezclas de triángulos isósceles y triángulos equiláteros. (Se sabe que hay exactamente 8 poliedros convexos con solo triángulos equiláteros por caras). Uno de los puntos conflictivos de estas preguntas es tratar de saber cuándo dos triángulos que comparten un borde en el gráfico se aplanan y se encuentran en un plano en la realización en 3 espacios.
Sin embargo, mi punto es que el teorema de Steinitz permitió avanzar en muchas preguntas y me animó a formular nuevas preguntas geométricas que no se me habrían ocurrido de otra manera.
Mejor,
Joe Malkevitch
Otra caracterización (menos conocida) de las gráficas planas es el teorema de Schnyder, que caracteriza las gráficas planas según la dimensión del orden. Es decir, un gráfico es plano si y solo si su posición de incidencia tiene una dimensión de orden como máximo 3.
Además, sería negligente no mencionar a la hermosa (fuerte) Teorema de Hanani-Tutte:
Una gráfica es plana si y solo si tiene un dibujo en el plano tal que cada dos aristas no adyacentes cruzan una incluso numero de veces.
Si te animas, puedes dejar una reseña acerca de qué le añadirías a este enunciado.