En teoría de grafos , el teorema de Schnyder es una caracterización de los grafos planos en términos de la dimensión de orden de sus conjuntos parciales de incidencia . Recibe su nombre en honor a Walter Schnyder, quien publicó su demostración en 1989.
El conjunto 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 puntos extremos de y .
La dimensión de orden de un orden parcial es el número más pequeño de ordenamientos totales cuya intersección es el orden parcial dado; dicho conjunto de ordenamientos se denomina realizador del orden parcial. El teorema de Schnyder establece que un grafo G es plano si y solo si la dimensión de orden de P ( G ) es como máximo tres.
Brightwell y Trotter (1993, 1997) han generalizado este teorema para limitar estrictamente la dimensión de los conjuntos parcialmente ordenados de altura-tres formados de forma análoga a partir de los vértices, aristas y caras de un poliedro convexo o, de forma más general, de un grafo plano embebido: en ambos casos, la dimensión de orden del conjunto parcial es como máximo cuatro. Sin embargo, este resultado no se puede generalizar a politopos convexos de dimensiones superiores , ya que existen politopos de cuatro dimensiones cuyas redes de caras tienen una dimensión de orden ilimitada.
De manera aún más general, para complejos simpliciales abstractos , la dimensión de orden del conjunto 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 de elementos 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, en cuando un conjunto de elementos 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 de elementos de incidencia. Para estos dos órdenes en los vértices, se puede incluir una arista entre vértices consecutivos en el ordenamiento colocándola inmediatamente después del último de los dos puntos finales de la arista, pero no se pueden incluir otras aristas.
Si un gráfico se puede colorear con cuatro colores, entonces su conjunto poset de incidencia tiene una dimensión de orden de como máximo cuatro (Schnyder 1989).
El conjunto de posiciones de incidencia de un gráfico completo en n vértices tiene dimensión de orden (Spencer 1971).
