En teoría de grafos , el teorema de Schnyder es una caracterización de grafos planares en términos de la dimensión de orden de sus posets de incidencia . Lleva el nombre de Walter Schnyder, quien publicó su prueba en 1989 .
El poset de incidencia P ( G ) de un grafo no dirigido G con el conjunto de vértices V y el conjunto de bordes E es el conjunto parcialmente ordenado de altura 2 que tiene V ∪ E como sus elementos. En este orden parcial, hay 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 una orden parcial es el número más pequeño de órdenes totales cuya intersección es la orden parcial dada; tal conjunto de ordenamientos se llama un realizador del orden parcial. El teorema de Schnyder establece que una gráfica G es plana si y solo si la dimensión de orden de P ( G ) es como máximo tres.
Este teorema ha sido generalizado por Brightwell y Trotter ( 1993 , 1997 ) a un límite estrecho en la dimensión de la altura: tres conjuntos parcialmente ordenados formados de manera análoga a partir de los vértices, aristas y caras de un poliedro convexo , o más generalmente de un plano incrustado. gráfico: en ambos casos, la dimensión de orden del poset 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 celosías faciales tienen una dimensión de orden ilimitada.
Incluso de manera más general, para los complejos simpliciales abstractos , la dimensión de orden del poset facial 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 incidencia de un gráfico G tiene una dimensión de orden dos si y solo si el gráfico es una ruta o un subgrafo de una ruta. Porque, cuando una posición de incidencia tiene una dimensión de orden es dos, su único realizador posible consiste en dos órdenes totales que (cuando se restringen a los vértices del gráfico) son inversas entre sí. Cualesquiera otros dos órdenes tendrían una intersección que incluye una relación de orden entre dos vértices, lo cual no está permitido para posets de incidencia. Para estos dos órdenes en los vértices, se puede incluir un borde entre vértices consecutivos en el orden colocándolo inmediatamente después del último de los dos extremos del borde, pero no se pueden incluir otros bordes.