Teorema de Schnyder

En teoría de grafos , el teorema de Schnyder caracteriza los grafos planares en términos de la dimensión de orden de sus conjuntos parcialmente ordenados de incidencia . Recibe su nombre de Walter Schnyder, quien publicó su demostración en 1989 .

El poset de incidencia P ( G ) de un grafo no dirigido G con conjunto de vértices V y conjunto de aristas E es el conjunto parcialmente ordenado de altura 2 que tiene V ∪ E como sus elementos. En este orden parcial, existe una relación de orden x < y cuando x es un vértice, y es una arista y x es uno de los dos extremos de y .

La dimensión de orden de un orden parcial es el número más pequeño de ordenaciones totales cuya intersección es el orden parcial dado; dicho conjunto de ordenaciones se denomina realizador del orden parcial. El teorema de Schnyder establece que un grafo G es planar si y solo si la dimensión de orden de P ( G ) es como máximo tres.

Este teorema fue generalizado por Brightwell y Trotter ( 1993 , 1997 ) a una cota ajustada para la dimensión de los conjuntos parcialmente ordenados de altura tres formados análogamente a partir de los vértices, aristas y caras de un poliedro convexo , o más generalmente de un grafo planar incrustado: en ambos casos, la dimensión de orden del conjunto parcialmente ordenado es como máximo cuatro. Sin embargo, este resultado no puede generalizarse a politopos convexos de dimensiones superiores , ya que existen politopos de cuatro dimensiones cuyas redes de caras tienen una dimensión de orden no acotada. 

De manera aún más general, para complejos simpliciales abstractos , la dimensión de orden del poset de caras del complejo es como máximo 1 + d , donde d es la dimensión mínima de un espacio euclidiano en el que el complejo tiene una realización geométrica (Ossona de Méndez 1999 , 2002 ) . 

Como observa Schnyder, el conjunto parcialmente ordenado de incidencia de un grafo G tiene dimensión de orden dos si y solo si el grafo es un camino o un subgrafo de un camino. Porque, cuando un conjunto parcialmente ordenado de incidencia tiene dimensión de orden dos, su único realizador posible consiste en dos órdenes totales que (cuando se restringen a los vértices del grafo) son inversos entre sí. Cualquier otro par de órdenes tendría una intersección que incluye una relación de orden entre dos vértices, lo cual no está permitido para los conjuntos parcialmente ordenados de incidencia. Para estos dos órdenes en los vértices, una arista entre vértices consecutivos puede incluirse en el ordenamiento colocándola inmediatamente después del último de los dos extremos de la arista, pero no se pueden incluir otras aristas.

Si un grafo puede colorearse con cuatro colores, entonces su poset de incidencia tiene una dimensión de orden como máximo cuatro ( Schnyder 1989 ) .

El poset de incidencia de un grafo completo en n vértices tiene dimensión de orden${\displaystyle \Theta (\log \log n)}$( Spencer 1971 ) .

• Brightwell, G.; Trotter, WT (1993), "La dimensión de orden de los politopos convexos", SIAM Journal on Discrete Mathematics , 6 (2): 230– 245, doi : 10.1137/0406018 , MR 1215230 .
• Brightwell, G.; Trotter, WT (1997), "La dimensión de orden de los mapas planares", SIAM Journal on Discrete Mathematics , 10 (4): 515– 528, CiteSeerX 10.1.1.127.1016 , doi : 10.1137/S0895480192238561 , MR 1477654  .
• Ossona de Méndez, P. (1999), "Realización geométrica de complejos simpliciales", en Kratochvil, J. (ed.), Proc. Int. Symp. Graph Drawing (GD 1999) , Lecture Notes in Computer Science, vol.  1731, Springer-Verlag, pp. 323–332 , doi : 10.1007/3-540-46648-7_33 , ISBN  978-3-540-66904-3, MR 1856785 .
• Ossona de Méndez, P. (2002), "Realización de conjuntos parcialmente ordenados" (PDF) , Journal of Graph Algorithms and Applications , 6 (1): 149– 153, doi : 10.7155/jgaa.00048 , MR 1898206 .
• Schnyder, W. (1989), "Grafos planares y dimensión de conjuntos parcialmente ordenados", Order , 5 (4): 323– 343, doi : 10.1007/BF00353652 , MR 1010382 , S2CID 122785359  .
• Spencer, J. (1971), "Conjuntos de codificación mínimos de órdenes simples", Acta Mathematica Academiae Scientiarum Hungaricae , 22 ( 3– 4): 349– 353, doi : 10.1007/bf01896428 , MR 0292722 , S2CID 123142998  .