El teorema de Steinitz es una descripción combinatoria de gráficos no dirigidos formados por las aristas y los vértices de un poliedro convexo 3D : son exactamente ( simples ) gráficos planos conectados por 3 vértices (con al menos cuatro vértices) [1] [2] . Es decir, cualquier politopo convexo forma un gráfico plano de 3 conexiones, y cualquier gráfico plano de 3 conexiones se puede representar como un politopo convexo. Por esta razón, los grafos planos conectados en 3 también se denominan poliédricos [3] .
El teorema de Steinitz lleva el nombre de Ernst Steinitz , quien publicó la primera demostración de este resultado en 1916 [4] . Branko Grünbaum llamó a este teorema "el resultado más importante y más profundo sobre poliedros tridimensionales " [2] .
El nombre "teorema de Steinitz" también es aplicable a otros resultados de Steinitz:
Un grafo no dirigido es un sistema de vértices y aristas , cada arista conecta dos vértices. Se puede formar un gráfico a partir de cualquier poliedro si los vértices del gráfico se toman como los vértices del poliedro y dos vértices del gráfico están conectados por una arista si los vértices correspondientes del poliedro son los puntos finales de sus aristas. Este gráfico se conoce como el esqueleto unidimensional del poliedro.
Un gráfico es plano si sus vértices se pueden colocar en un plano y las aristas del gráfico se pueden dibujar en este plano como curvas que conectan estos puntos, de tal manera que dos aristas no se cortan, y los vértices se encuentran en dichas curvas, si sólo el vértice es el punto final de la arista correspondiente. Por el teorema de Fari , podemos suponer que las curvas son, de hecho, segmentos . Un grafo es conexo con 3 vértices si, después de eliminar dos de sus vértices, cualquier par de los vértices restantes se pueden conectar mediante un camino.
El enunciado del teorema de Steinitz en una dirección (más fácil de demostrar) dice que el gráfico de cualquier politopo convexo es plano y triconexo. Como se muestra en la figura, la planaridad se puede mostrar usando un diagrama de Schlegel : si coloca una fuente de luz puntual cerca de una de las caras del poliedro y coloca un plano en el otro lado, las sombras de los bordes del poliedro forman un gráfico plano incrustado en el plano de tal manera que los bordes del gráfico se representan como segmentos. La 3-conectividad de un grafo de politopo es un caso especial del teorema de Balinsky de que el grafo de cualquier politopo convexo de dimensión k es k - conexo [11] .
El enunciado de otra manera más complicada dice que cualquier gráfico plano conectado en 3 es un gráfico de un poliedro convexo.
Se puede demostrar una afirmación más rigurosa del teorema de Steinitz, que cualquier gráfico poliédrico se puede realizar como un poliedro convexo con vértices que tienen coordenadas enteras. Los números enteros obtenidos en la prueba original de Steinitz son una función doblemente exponencial del número de vértices del poliedro dado. Por lo tanto, escribir estos números requiere un número exponencial de bits [12] . Sin embargo, investigaciones posteriores encontraron un algoritmo de visualización de gráficos que requiere solo O( n ) bits para cada vértice [13] [14] . Podemos relajar el requisito de que todas las coordenadas sean números enteros y asignar coordenadas de tal manera que las coordenadas x de los vértices sean números enteros diferentes en el intervalo [0,2 n − 4], y las otras dos coordenadas serán números reales en el intervalo [0,1], de modo que cada arista tenga una longitud de al menos uno, mientras que el volumen del poliedro estará limitado a O( n ) [15] .
En cualquier politopo que represente un gráfico poliédrico G dado , las caras de G son exactamente ciclos en G que no dividen a G en dos componentes. Es decir, quitar el ciclo correspondiente a una cara de G da un subgrafo conexo de G. Puede especificar la forma de cualquier cara del poliedro de antemano: si elige un ciclo C que no divide el gráfico en partes y organiza sus vértices en forma de un polígono convexo bidimensional P , entonces hay un representación poliédrica G , en la que la cara correspondiente a C es congruente con P [16] . También siempre es posible para un gráfico poliédrico G y un ciclo C arbitrario encontrar una realización en la que C forma una silueta de realización bajo una proyección paralela [17] .
El teorema de empaquetamiento de círculos de Köbe-Andreev- Thurston puede verse como otro refuerzo del teorema de Steinitz de que cualquier gráfico plano conectado en 3 se puede representar como un poliedro convexo de tal manera que todos sus bordes toquen la misma esfera unitaria [ 18] . Más generalmente, si G es un gráfico poliédrico y K es un cuerpo convexo tridimensional suave , uno puede encontrar una representación poliédrica de G en la que todos los bordes tocan K [19] .