Integración combinatoria de un gráfico

12

Aquí: http://www.planarity.org/Klein_elementary_graph_theory.pdf (en incrustaciones de capítulos) se le da la definición de incrustación combinatoria de un gráfico plano. (con definición de caras, etc.) Aunque podría usarse fácilmente para cualquier gráfico, definen el gráfico plano como el gráfico, para el cual se mantiene la fórmula de Euler (suponiendo que el gráfico esté conectado). Es bastante comprensible que para cada gráfico plano la definición de caras en la incrustación combinatoria sea similar a la definición de caras en la incrustación topológica. (suponiendo que el gráfico esté conectado. De lo contrario, en la incrustación combinatoria tendremos una cara infinita para cada componente conectado)

La pregunta es: si para algún gráfico conectado, su incrustación combinatoria satisface la fórmula de Euler, ¿significa esto que este gráfico es plano en sentido topológico (tiene incrustación plana, es decir, es un gráfico plano )?

graph-theory co.combinatorics planar-graphs Finsky
fuente
Más adelante en este documento dan una respuesta de que esto es posible. ¿Pero alguien puede dar algunos enlaces a la prueba?
Finsky

Respuestas:

16

Esto realmente es menos sobre el gráfico per se y más sobre la topología. Una incrustación combinatoria define un 2-múltiple, un espacio topológico en el que cada punto tiene un vecindario homeomorfo a un disco abierto bidimensional: la incrustación permite definir una cara, y podemos definir un espacio topológico eligiendo un disco para cada enfrentarlos y pegarlos a lo largo de los bordes del gráfico. Un teorema bien conocido en topología (llamado clasificación de 2 múltiples) nos dice exactamente qué 2 múltiples son posibles, y todos se pueden distinguir entre sí, ya sea si son orientables o si tienen la misma característica de Euler (o ambos ) - ver http://www.maths.ed.ac.uk/~aar/surgery/zeeman.pdfpara algunas notas de clase razonables sobre este tema, que incluyen la prueba que está solicitando. No hay otros 2 múltiples en esta clasificación que tengan la misma característica de Euler que la esfera, por lo que si calcula la característica de Euler y descubre que coincide con la fórmula de una esfera, sabe que su incrustación debe estar en una esfera.

Encontrar una incrustación con coordenadas geométricas reales en el plano, una vez que tiene una incrustación combinatoria plana, no es del todo trivial, pero se puede hacer, por ejemplo, utilizando la teoría de las maderas de Schnyder. Tengo algunas notas sobre esto en http://www.ics.uci.edu/~eppstein/gina/schnyder/ por ejemplo.

David Eppstein
fuente
¡Muchas gracias por una respuesta tan extensa! He leído el primer artículo y parece que entendí la prueba. Pero me queda una pregunta: ¿significa todo esto que si definiremos las superficies como queramos (me refiero a un subconjunto arbitrario de bordes, no como en la incrustación combinatoria con orden y cosas en sentido contrario a las agujas del reloj), pegarlos todos de tal manera que el pegamento es solo para compartir bordes de 2 superficies, define los 'nudos' resultantes en los puntos finales de los bordes como vértices Y si la fórmula de Euler es válida, ¿es un gráfico plano?
Finsky
1
Debe tener cuidado de obtener una variedad: las caras de la incrustación deben ser discos topológicos, no puede dejar bordes sin pegar, cada borde solo debe estar pegado a otro borde, y en cada vértice solo debe haber un ciclo de bordes y caras pegados a su alrededor (no como lo que obtienes si pegas dos conos juntos en sus puntas). También debe comenzar con un gráfico conectado o contar la característica de Euler para cada componente por separado. Pero si todo eso es cierto, y la fórmula de Euler es válida, entonces sí, es plana.
David Eppstein
Sí, olvidé esos casos, seguro que también tienen que aguantar. ¡Muchas gracias!
Finsky