Un grafo no dirigido es un sistema de vértices y aristas, cada una de las cuales conecta dos de los vértices. Como es habitual en la teoría de grafos, a efectos del teorema de Steinitz estos grafos se limitan a ser finitos (los vértices y las aristas son conjuntos finitos) y simples (no hay dos aristas que conecten los dos mismos vértices, y ninguna arista conecta un vértice consigo misma). A partir de cualquier poliedro se puede formar un grafo, haciendo que los vértices del grafo correspondan a los vértices del poliedro y conectando dos vértices cualesquiera del grafo mediante una arista siempre que los dos vértices correspondientes del poliedro sean los puntos extremos de una arista del poliedro. Este grafo se conoce como el esqueleto del poliedro.^[7]​

Un grafo es plano si se puede dibujar con sus vértices como puntos en el plano euclídeo, y sus aristas como curvas que conectan estos puntos, de forma que no se crucen dos curvas de arista y que el punto que representa un vértice se encuentre en la curva que representa una arista sólo cuando el vértice es un extremo de la arista. Por el teorema de Fáry, todo dibujo plano puede enderezarse de modo que las curvas que representan las aristas sean segmentos rectos. Un grafo está 3-conectado si tiene más de tres vértices y, tras la eliminación de dos de sus vértices cualesquiera, cualquier otro par de vértices permanece conectado por un camino. El teorema de Steinitz afirma que estas dos condiciones son necesarias y suficientes para caracterizar los esqueletos de los poliedros convexos tridimensionales: un grafo dado ${\displaystyle G}$  es el gráfico de un poliedro tridimensional convexo, si y sólo si ${\displaystyle G}$  es plano y está conectado por 3 vértices.^[5]​^[8]​

Una de las direcciones del teorema de Steinitz (la más fácil de demostrar) afirma que el grafo de todo poliedro convexo es plano y está conectado por 3 puntos. Como se muestra en la ilustración, la planaridad puede demostrarse utilizando un diagrama de Schlegel: si se coloca una fuente de luz cerca de una cara del poliedro, y un plano en la otra cara, las sombras de las aristas del poliedro formarán un grafo planar, incrustado de tal manera que las aristas son segmentos de línea recta. La 3-conectividad de un grafo poliédrico es un caso especial del teorema de Balinski según el cual el grafo de cualquier ${\displaystyle k}$  dimensional politopo convexo está ${\displaystyle k}$  conectado. La conectividad del grafo de un politopo, después de eliminar cualquier ${\displaystyle k-1}$  de sus vértices, puede demostrarse eligiendo un vértice más ${\displaystyle v}$ , encontrando una función lineal que sea cero en el conjunto resultante de vértices ${\displaystyle k}$  y siguiendo los caminos generados por el método simplex para conectar cada vértice con uno de los dos vértices extremos de la función lineal, con el vértice elegido ${\displaystyle v}$  conectado a ambos.^[9]​

La otra dirección, más difícil, del teorema de Steinitz afirma que todo grafo plano de 3 conexiones es el grafo de un poliedro convexo. Existen tres enfoques estándar para esta parte: pruebas por inducción, elevación de embebidos bidimensionales de Tutte a tres dimensiones mediante la correspondencia Maxwell-Cremona y métodos que utilizan el teorema del empaquetamiento de circunferencia para generar un poliedro canónico.

Aunque la prueba original de Steinitz no se expresó en términos de teoría de grafos, puede reescribirse en esos términos y consiste en encontrar una secuencia de transformaciones ΔY- e YΔ que reducen cualquier grafo plano de 3 conexiones a ${\displaystyle K_{4}}$ , el grafo del tetraedro. Una transformación Y elimina un vértice de grado tres de un grafo, añadiendo aristas entre todos sus vecinos anteriores si esas aristas no existían ya; la transformación inversa, una transformación ΔY, elimina las aristas de un triángulo de un grafo y las sustituye por un nuevo vértice de grado tres adyacente a los mismos tres vértices. Una vez encontrada una secuencia de este tipo, puede invertirse y convertirse en operaciones geométricas que construyan paso a paso el poliedro deseado partiendo de un tetraedro. Cada transformación Y de la secuencia inversa puede realizarse geométricamente cortando un vértice de grado tres de un poliedro. Una transformación ΔY en la secuencia inversa puede realizarse geométricamente eliminando una cara triangular de un poliedro y extendiendo sus caras vecinas hasta el punto donde se encuentran, pero sólo cuando ese punto de intersección triple de las tres caras vecinas está en el lado más alejado de la cara eliminada del poliedro. Cuando el punto de triple intersección no está en el lado lejano de esta cara, basta una transformación proyectiva del poliedro para moverlo al lado correcto. Por tanto, por inducción sobre el número de transformaciones ΔY- e YΔ necesarias para reducir un grafo dado a ${\displaystyle K_{4}}$ , todo grafo poliédrico puede realizarse como un poliedro.^[5]​

Un trabajo posterior de Epifanov reforzó la prueba de Steinitz de que todo grafo poliédrico puede reducirse a ${\displaystyle K_{4}}$  mediante transformaciones ΔY- e YΔ. Epifanov demostró que si se especifican dos vértices en un grafo plano, entonces el grafo puede reducirse a una sola arista entre esos terminales combinando transformaciones ΔY- e YΔ con reducciones serie-paralelo.^[10]​ La prueba de Epifanov era complicada y no constructiva, pero fue simplificada por Truemper usando métodos basados en menores de grafos. Truemper observó que todo grafo reticular es reducible mediante transformaciones ΔY- e YΔ de este modo, que esta reducibilidad se conserva mediante menores de grafos, y que todo grafo plano es un menor de un grafo reticular.^[11]​ Esta idea puede utilizarse para sustituir el lema de Steinitz de que existe una secuencia de reducción. Después de esta sustitución, el resto de la demostración se puede llevar a cabo utilizando la inducción de la misma manera que la demostración original de Steinitz.^[8]​ Para estas demostraciones, llevadas a cabo utilizando cualquiera de las formas de encontrar secuencias de ΔY- e YΔ-transformaciones, existen grafos poliédricos que requieren un número no lineal de pasos. Más concretamente, todo grafo plano puede reducirse utilizando un número de pasos como máximo proporcional a ${\displaystyle n^{3/2}}$ , e infinitas gráficas requieren un número de pasos al menos proporcional a ${\displaystyle n^{3/2}}$ , donde ${\displaystyle n}$  es el número de vértices del grafo.^[12]​^[13]​

Una forma alternativa de prueba por inducción se basa en eliminar aristas (y comprimir los vértices de grado dos que puedan quedar tras esta eliminación) o contraer aristas y formar un menor del grafo plano dado. Cualquier grafo poliédrico puede reducirse a ${\displaystyle K_{4}}$  por un número lineal de estas operaciones, y de nuevo las operaciones pueden invertirse y las operaciones invertidas realizarse geométricamente, dando una realización poliédrica del grafo. Sin embargo, aunque es más sencillo demostrar que existe una secuencia de reducción para este tipo de argumento, y las secuencias de reducción son más cortas, los pasos geométricos necesarios para invertir la secuencia son más complicados.^[14]​

Si se dibuja un gráfico en el plano con aristas rectilíneas, se define una tensión de equilibrio como una asignación de números reales distintos de cero

(pesos) a las aristas, con la propiedad de que cada vértice está en la posición dada por la media ponderada de sus vecinos. Según la correspondencia Maxwell-Cremona, una tensión de equilibrio puede elevarse a una superficie tridimensional continua lineal a trozos tal que las aristas que forman los límites entre las partes planas de la superficie se proyecten al dibujo dado. El peso y la longitud de cada arista determinan la diferencia de pendientes de la superficie a ambos lados de la arista, y la condición de que cada vértice esté en equilibrio con sus vecinos equivale a la condición de que estas diferencias de pendientes hagan que la superficie se encuentre consigo misma correctamente en la vecindad del vértice. Los pesos positivos se traducen en ángulos diedros convexos entre dos caras de la superficie lineal a trozos, y los pesos negativos se traducen en ángulos diedros cóncavos. A la inversa, toda superficie lineal a trozos continua procede de una tensión de equilibrio de este modo. Si se dibuja un grafo plano finito y se le da una tensión de equilibrio de tal forma que todas las aristas interiores del dibujo tengan pesos positivos, y todas las aristas exteriores tengan pesos negativos, al trasladar esta tensión a una superficie tridimensional de esta forma, y luego sustituir la superficie plana que representa el exterior del grafo por su complemento en el mismo plano, se obtiene un poliedro convexo, con la propiedad adicional de que su proyección perpendicular sobre el plano no tiene cruces.^[15]​^[16]​

La correspondencia Maxwell-Cremona se ha utilizado para obtener realizaciones poliédricas de grafos poliédricos combinándola con un método de dibujo de grafos en el plano de W. T. Tutte, el embedido de Tutte. El método de Tutte comienza fijando una cara de un grafo poliédrico en posición convexa en el plano. Esta cara se convertirá en la cara exterior del dibujo de un grafo. El método continúa estableciendo un sistema de ecuaciones lineales en las coordenadas de los vértices, según el cual cada vértice restante debe situarse en la media de sus vecinos. Entonces, como demostró Tutte, este sistema de ecuaciones tendrá una solución única en la que cada cara del grafo se dibuja como un polígono convexo.^[17]​ Intuitivamente, esta solución describe el patrón que se obtendría sustituyendo las aristas interiores del grafo por muelles ideales y dejando que se asienten en su estado de mínima energía.^[18]​ El resultado es casi una tensión de equilibrio: si se asigna peso uno a cada arista interior, entonces cada vértice interior del dibujo está en equilibrio. Sin embargo, no siempre es posible asignar números negativos a las aristas exteriores para que también estén en equilibrio. Dicha asignación siempre es posible cuando la cara exterior es un triángulo, por lo que este método puede utilizarse para realizar cualquier grafo poliédrico que tenga una cara triangular. Si un grafo poliédrico no contiene una cara triangular, su grafo dual contiene un triángulo y también es poliédrico, por lo que se puede realizar el dual de esta manera y luego realizar el grafo original como el poliedro polar de la realización dual.^[4]​^[19]​ Un método alternativo para realizar poliedros utilizando elevaciones evita la dualidad mediante la elección de cualquier cara con un máximo de cinco vértices como la cara exterior. Todo grafo poliédrico tiene una cara de este tipo, y eligiendo la forma fija de esta cara con más cuidado, se puede levantar la incrustación de Tutte del resto del grafo.^[20]​

Según una variante del teorema de empaquetamiento de circunferencias, para todo grafo poliédrico existe un sistema de círculos en el plano o en cualquier esfera, que representan los vértices y las caras del grafo, de modo que:

• cada dos vértices adyacentes del grafo están representados por círculos tangentes,
• cada dos caras adyacentes del grafo están representadas por círculos tangentes,
• cada par de un vértice y una cara a la que toca están representados por círculos que se cruzan en ángulo recto, y
• todos los demás pares de círculos están separados entre sí.^[21]​

El mismo sistema de círculos forma una representación del grafo dual intercambiando los papeles de los círculos que representan los vértices y los círculos que representan las caras. A partir de cualquier representación de este tipo en una esfera, incrustada en un espacio euclidiano tridimensional, se puede formar un poliedro convexo que es combinatoriamente equivalente al grafo dado, como una intersección de semiespacios cuyos límites pasan por los círculos de las caras. A partir de cada vértice de este poliedro, el horizonte en la esfera, visto desde ese vértice, es el círculo que lo representa. Esta propiedad del horizonte determina la posición tridimensional de cada vértice, y el poliedro puede definirse equivalentemente como el envolvente convexo de los vértices, colocados de esta forma. La esfera se convierte en la semiesfera de la realización: cada arista del poliedro es tangente a la esfera, en un punto donde dos círculos tangentes a los vértices cruzan dos círculos tangentes a las caras.^[22]​

Es posible demostrar una forma más fuerte del teorema de Steinitz, según la cual cualquier grafo poliédrico puede realizarse mediante un poliedro convexo cuyas coordenadas son números enteros.^[23]​ Por ejemplo, la prueba original de Steinitz, basada en la inducción, puede reforzarse de este modo. Sin embargo, los números enteros que resultarían de la construcción de Steinitz son doblemente exponenciales en el número de vértices del grafo poliédrico dado. Escribir números de esta magnitud en notación binaria requeriría un número exponencial de bits.^[19]​ Geométricamente, esto significa que algunas características del poliedro pueden tener un tamaño doblemente exponencial más grande que otras, haciendo que las realizaciones derivadas de este método sean problemáticas para aplicaciones en el dibujo de grafos.^[4]​

Investigadores posteriores han encontrado algoritmos de realización basados en la elevación que utilizan sólo un número lineal de bits por vértice.^[20]​ ^[24]​También es posible relajar el requisito de que las coordenadas sean enteras, y asignar coordenadas de tal manera que las coordenadas ${\displaystyle x}$  de los vértices sean enteros distintos en el rango de 0 a ${\displaystyle 2n-4}$  y las otras dos coordenadas son números reales en el intervalo unitario, de modo que cada arista tiene longitud al menos uno mientras que el poliedro total tiene volumen lineal.^[25]​^[26]​ Se sabe que algunos grafos poliédricos son realizables en cuadrículas de tamaño sólo polinómico; en particular esto es cierto para las pirámides (realizaciones de grafos rueda), prismas (realizaciones de grafos de prismas), y poliedros apilados (realizaciones de grafos apolíneos).^[27]​

Otra forma de afirmar la existencia de realizaciones enteras es que todo poliedro convexo tridimensional tiene un poliedro entero combinatoriamente equivalente.^[23]​ Por ejemplo, el dodecaedro regular no es en sí mismo un poliedro entero, debido a sus caras de pentágono regular, pero puede realizarse como un piritoedro entero equivalente.^[20]​ Esto no siempre es posible en dimensiones superiores, donde existen politopos (como los construidos a partir de la configuración de Perles) que no tienen equivalente entero.^[28]​

Un grafo de Halin es un caso especial de grafo poliédrico, formado a partir de un árbol plano (sin vértices de grado dos) conectando las hojas del árbol en un ciclo. Para los grafos de Halin, se pueden elegir realizaciones poliédricas de un tipo especial: el ciclo exterior forma una cara base convexa horizontal, y todas las demás caras se sitúan directamente sobre la cara base (como en los poliedros realizados mediante elevación), teniendo todas estas caras superiores la misma pendiente. Las superficies poliédricas con caras de igual pendiente sobre cualquier polígono base (no necesariamente convexo) pueden construirse a partir del esqueleto recto del polígono, y una forma equivalente de describir esta realización es que la proyección bidimensional del árbol sobre la cara base forma su esqueleto recto. La prueba de este resultado utiliza la inducción: cualquier árbol enraizado puede reducirse a un árbol más pequeño eliminando las hojas de un nodo interno cuyos hijos son todos hojas, el grafo de Halin formado a partir del árbol más pequeño tiene una realización por la hipótesis de inducción, y es posible modificar esta realización para añadir cualquier número de hijos hojas al nodo del árbol cuyos hijos se eliminaron.^[29]​

En cualquier poliedro que represente un grafo poliédrico dado ${\displaystyle G}$ , las caras de ${\displaystyle G}$  son exactamente los ciclos de ${\displaystyle G}$  que no separan ${\displaystyle G}$  en dos componentes: es decir, eliminar un ciclo facial de ${\displaystyle G}$  deja el resto de ${\displaystyle G}$  como un subgrafo conexo. Tales ciclos se denominan ciclos periféricos. Así, la estructura combinatoria de las caras (pero no sus formas geométricas) se determina de forma única a partir de la estructura del grafo. Otro refuerzo del teorema de Steinitz, de Barnette y Grünbaum, afirma que para cualquier grafo poliédrico, cualquier cara del grafo y cualquier polígono convexo que represente esa cara, es posible encontrar una realización poliédrica del grafo completo que tenga la forma especificada para la cara designada. Esto está relacionado con un teorema de Tutte, según el cual cualquier grafo poliédrico puede dibujarse en el plano con todas las caras convexas y cualquier forma especificada para su cara exterior. Sin embargo, los dibujos de grafos planos producidos por el método de Tutte no se elevan necesariamente a poliedros convexos. En su lugar, Barnette y Grünbaum demuestran este resultado utilizando un método inductivo.^[30]​ También es siempre posible, dado un grafo poliédrico ${\displaystyle G}$  y un ciclo arbitrario ${\displaystyle C}$  en ${\displaystyle G}$ , encontrar una realización para la que ${\displaystyle C}$  forme la silueta de la realización bajo proyección paralela.^[31]​

La realización de poliedros utilizando el teorema de empaquetamiento de circunferencias proporciona otro refuerzo del teorema de Steinitz: todo grafo plano de 3 conexiones puede representarse como un poliedro convexo de forma que todas sus aristas sean tangentes a la misma esfera unitaria, la semiesfera del poliedro.^[22]​ Realizando una transformación de Möbius cuidadosamente elegida de un empaquetamiento de circunferencias antes de transformarlo en un poliedro, es posible encontrar una realización poliédrica que realice todas las simetrías del grafo subyacente, en el sentido de que cada automorfismo del grafo es una simetría de la realización poliédrica.^[32]​^[33]​ En términos más generales, si ${\displaystyle G}$  es un grafo poliédrico y ${\displaystyle K}$  es cualquier cuerpo convexo tridimensional liso, es posible encontrar una representación poliédrica de ${\displaystyle G}$  en la que todas las aristas sean tangentes a ${\displaystyle K}$ .^[34]​

Los métodos de empaquetamiento en círculos también pueden utilizarse para caracterizar los grafos de poliedros que tienen una circunsfera que pasa por todos sus vértices, o una insfera tangente a todas sus caras. (Los poliedros con una circunsfera también son significativos en geometría hiperbólica como los poliedros ideales). En ambos casos, la existencia de una esfera es equivalente a la resolubilidad de un sistema de inecuaciones lineales sobre variables reales positivas asociado a cada arista del grafo. En el caso de la insfera, estas variables deben sumar exactamente uno en cada ciclo de cara del grafo, y más de uno en cada ciclo que no sea de cara. En el caso de la circunsfera, las variables deben sumar una en cada vértice y más de una en cada corte con dos o más vértices a cada lado del corte. Aunque puede haber exponencialmente muchas desigualdades lineales que satisfacer, una solución (si existe) se puede encontrar en tiempo polinómico utilizando el método del elipsoide. Los valores de las variables de una solución determinan los ángulos entre pares de círculos en un empaquetamiento de círculos cuyo poliedro correspondiente tiene la relación deseada con su esfera.^[35]​^[36]​

En cualquier dimensión superior a tres, el problema algorítmico de Steinitz consiste en determinar si una red dada es la red de caras de un politopo convexo. Es poco probable que tenga complejidad en tiempo polinómico, ya que es NP-difícil y más fuertemente completo para la teoría existencial de los reales, incluso para los politopos de cuatro dimensiones, por el teorema de universalidad de Richter-Gebert.^[38]​ Aquí, la teoría existencial de los reales es una clase de problemas computacionales que se pueden formular en términos de encontrar variables reales que satisfagan un sistema dado de ecuaciones polinómicas y desigualdades. Para el problema algorítmico de Steinitz, las variables de dicho problema pueden ser las coordenadas de los vértices de un politopo, y las ecuaciones y desigualdades pueden utilizarse para especificar la planitud de cada cara en la red de caras dada y la convexidad de cada ángulo entre caras. La completitud significa que cualquier otro problema de esta clase puede transformarse en una instancia equivalente del problema algorítmico de Steinitz, en tiempo polinómico. La existencia de tal transformación implica que, si el problema algorítmico de Steinitz tiene una solución en tiempo polinómico, entonces también la tienen todos los problemas de la teoría existencial de los reales y todos los problemas de NP.^[39]​ Sin embargo, dado que un grafo dado puede corresponder a más de una red de caras, es difícil extender este resultado de completitud al problema del reconocimiento de los grafos de 4 politopos. La determinación de la complejidad computacional de este problema de reconocimiento de grafos sigue abierta.^[40]​

Los investigadores también han encontrado caracterizaciones teóricas de los grafos de ciertas clases especiales de poliedros tridimensionales no convexos^[37]​^[41]​ y de politopos convexos cuatridimensionales.^[40]​^[42]​^[43]​ Sin embargo, en ambos casos, el problema general sigue sin resolverse. De hecho, incluso el problema de determinar qué grafos completos son los grafos de poliedros no convexos (que no sean ${\displaystyle K_{4}}$  para el tetraedro y ${\displaystyle K_{7}}$  para el poliedro de Császár) sigue sin resolverse.^[44]​

El teorema de Eberhard caracteriza parcialmente los conjuntos múltiples de polígonos que pueden combinarse para formar las caras de un poliedro convexo. Puede demostrarse formando un grafo plano de 3 conexiones con el conjunto dado de caras poligonales y aplicando a continuación el teorema de Steinitz para hallar una realización poliédrica de dicho grafo.^[3]​

László Lovász ha demostrado una correspondencia entre las representaciones poliédricas de grafos y las matrices que realizan los invariantes de grafos de Colin de Verdière de los mismos grafos. El invariante de Colin de Verdière es el corank máximo de una matriz de adyacencia ponderada del grafo, bajo algunas condiciones adicionales que son irrelevantes para los grafos poliédricos. Se trata de matrices cuadradas simétricas indexadas por los vértices, con el peso del vértice ${\displaystyle i}$  en el coeficiente diagonal ${\displaystyle M_{i,i}}$  y con el peso de la arista ${\displaystyle i,j}$  en los coeficientes no diagonales ${\displaystyle M_{i,j}}$  y ${\displaystyle M_{j,i}}$ . Cuando los vértices ${\displaystyle i}$  y ${\displaystyle j}$  no son adyacentes, el coeficiente ${\displaystyle M_{i,j}}$  debe ser cero. Este invariante es como máximo tres si y sólo si el grafo es un grafo plano. Como muestra Lovász, cuando el grafo es poliédrico, se puede obtener una representación del mismo como poliedro encontrando una matriz de adyacencia ponderada de corank tres, encontrando tres vectores que formen una base para su espacio nulo, utilizando los coeficientes de estos vectores como coordenadas para los vértices de un poliedro y escalando estos vértices adecuadamente.^[45]​

La historia del teorema de Steinitz es descrita por Grünbaum (2007),^[46]​ que señala su primera aparición de forma críptica en una publicación de Ernst Steinitz, escrita originalmente en 1916.^[6]​ Steinitz proporcionó más detalles en notas de conferencias posteriores, publicadas tras su muerte en 1928. Aunque los tratamientos modernos del teorema de Steinitz lo plantean como una caracterización grafo-teórica de los poliedros, Steinitz no utilizó el lenguaje de los grafos.^[46]​ La formulación grafo-teórica del teorema fue introducida a principios de los años 60 por Branko Grünbaum y Theodore Motzkin, y su demostración también se convirtió a la teoría de grafos en el texto de Grünbaum de 1967 Convex Polytopes.^[46]​ Los trabajos de Epifanov sobre las transformaciones ΔY- e YΔ, que refuerzan la demostración de Steinitz, fueron motivados por otros problemas distintos de la caracterización de los poliedros. Truemper (1989) atribuye a Grünbaum la observación de la relevancia de este trabajo para el teorema de Steinitz.^[11]​

La correspondencia Maxwell-Cremona entre diagramas de tensiones y levantamientos poliédricos fue desarrollada en una serie de artículos por James Clerk Maxwell entre 1864 y 1870, basándose en trabajos anteriores de Pierre Varignon, William Rankine y otros, y fue popularizada a finales del siglo XIX por Luigi Cremona.^[47]​ La observación de que esta correspondencia puede utilizarse con el embedido de Tutte para demostrar el teorema de Steinitz proviene de Eades & Garvan (1995);^[4]​ véase también Richter-Gebert (1996).^[38]​

El teorema del empaquetamiento de circunferencias fue demostrado por Paul Koebe en 1936^[48]​^[49]​ y (de forma independiente) por E. M. Andreev en 1970;^[49]​^[50]​ fue popularizado a mediados de la década de 1980 por William Thurston, a quien (a pesar de citar a Koebe y Andreev) se le suele atribuir el mérito de ser uno de sus descubridores.^[49]​ La versión del teorema de Andreev ya se había formulado como una caracterización tipo Steinitz para ciertos poliedros en el espacio hiperbólico,^[50]​ y el uso del empaquetamiento en círculos para realizar poliedros con semiesferas procede del trabajo de Thurston.^[51]​ El problema de caracterizar poliedros con esferas inscritas o circunscritas, eventualmente resuelto usando un método basado en realizaciones de empaquetamiento de círculos, se remonta a trabajos no publicados de René Descartes alrededor de 1630^[52]​ y a Jakob Steiner en 1832;^[35]​^[53]​ los primeros ejemplos de poliedros que no tienen realización con una circunsfera o insfera fueron dados por Steinitz en 1928.^[35]​^[54]​