En la combinatoria poliédrica , una rama de las matemáticas, el teorema de Steinitz es una caracterización de las gráficas no dirigidas formadas por las aristas y vértices de poliedros convexos tridimensionales : son exactamente las gráficas planas ( simples ) conectadas a 3 vértices (con al menos cuatro vértices). Es decir, cada poliedro convexo forma un gráfico plano de 3 conexiones, y cada gráfico plano de 3 conexiones se puede representar como el gráfico de un poliedro convexo. Por esta razón, las gráficas planas de 3 conexiones también se conocen como gráficas poliédricas . [1] Branko Grünbaum ha llamado a este teorema "el resultado conocido más importante y más profundo en 3-politopos ". [2]
El teorema aparece en un artículo de 1922 de Ernst Steinitz , de quien recibe su nombre. Puede probarse por inducción matemática (como hizo Steinitz), encontrando el estado de energía mínima de un sistema de resorte bidimensional y elevando el resultado a tres dimensiones, o usando el teorema del empaquetamiento circular . Se conocen varias extensiones del teorema, en las que el poliedro que realiza un gráfico dado tiene restricciones adicionales; por ejemplo, cada gráfica poliédrica es la gráfica de un poliedro convexo con coordenadas enteras, o la gráfica de un poliedro convexo cuyos bordes son tangentes a una esfera media común .
En dimensiones superiores, el problema de caracterizar las gráficas de politopos convexos permanece abierto.
Definiciones y enunciado del teorema.
Un gráfico no dirigido es un sistema de vértices y aristas , cada arista conecta dos de los vértices. A partir de cualquier poliedro se puede formar un gráfico, dejando que los vértices del gráfico correspondan a los vértices del poliedro y conectando dos vértices de gráfico cualesquiera por una arista siempre que los dos vértices correspondientes del poliedro sean los extremos de una arista del poliedro. Este gráfico se conoce como el esqueleto del poliedro. [3]
Un gráfico es plano si se puede dibujar con sus vértices como puntos en el plano euclidiano y sus aristas como curvas que conectan estos puntos, de modo que no se crucen dos curvas de aristas y de modo que el punto que representa un vértice se encuentre en la curva. representando una arista solo cuando el vértice es un punto final de la arista. Según el teorema de Fáry , es suficiente considerar solo dibujos planos en los que las curvas que representan los bordes son segmentos de línea . Un gráfico está conectado en 3 si, después de eliminar dos de sus vértices, cualquier otro par de vértices permanece conectado por una ruta. El teorema de Steinitz establece que estas dos condiciones son necesarias y suficientes para caracterizar los esqueletos de poliedros convexos tridimensionales: un gráfico G dado es el gráfico de un poliedro tridimensional convexo, si y solo si G es plano y de 3 vértices. conectado. [2] [4]
Historia y naming
El teorema de Steinitz lleva el nombre de Ernst Steinitz , quien presentó su primera prueba para su publicación en 1916. [5]
El nombre "teorema de Steinitz" también se ha aplicado a otros resultados de Steinitz:
- el lema de intercambio de Steinitz implica que cada base de un espacio vectorial tiene el mismo número de vectores, [6]
- el teorema de que si el casco convexo de un conjunto de puntos contiene una esfera unitaria, entonces el casco convexo de un subconjunto finito del punto contiene una esfera concéntrica más pequeña, [7] y
- Generalización vectorial de Steinitz del teorema de la serie de Riemann sobre los reordenamientos de series condicionalmente convergentes . [8] [9] [10] [11]
Pruebas
Una dirección del teorema de Steinitz (la dirección más fácil de probar) establece que la gráfica de cada poliedro convexo es plana y está conectada en 3. Como se muestra en la ilustración, la planicidad se puede mostrar usando un diagrama de Schlegel : si se coloca una fuente de luz cerca de una cara del poliedro y un plano en el otro lado, las sombras de los bordes del poliedro formarán un gráfico plano, incrustado de tal manera que los bordes sean segmentos de línea recta. La 3-conectividad de un gráfico poliédrico es un caso especial del teorema de Balinski de que el gráfico de cualquier politopo convexo k -dimensional está k -conectado. [12]
La otra dirección, más difícil, del teorema de Steinitz establece que todo gráfico plano conectado de 3 es el gráfico de un poliedro convexo. Hay tres enfoques estándar para esta parte: demostraciones por inducción, elevando incrustaciones bidimensionales de Tutte en tres dimensiones usando la correspondencia de Maxwell-Cremona, y métodos que usan el teorema de empaquetamiento circular para generar un poliedro canónico .
Inducción
La prueba original de Steinitz implicaba encontrar una secuencia de transformaciones Δ-Y e Y-Δ que reducen cualquier gráfico plano de 3 conexiones a K 4 , el gráfico del tetraedro. Una transformada Y-Δ elimina un vértice de grado tres de un gráfico, agregando bordes entre todos sus vecinos anteriores si esos bordes no existían todavía; la transformación inversa, una transformada Δ-Y, elimina los bordes de un triángulo de un gráfico y los reemplaza por un nuevo vértice de grado tres adyacente a los mismos tres vértices. Una vez que se encuentra dicha secuencia, se puede revertir y convertir en operaciones geométricas que construyen el poliedro deseado paso a paso a partir de un tetraedro. Cada transformada Y-Δ en la secuencia inversa se puede realizar geométricamente cortando un vértice de grado tres de un poliedro. Una transformada Δ-Y en la secuencia inversa se puede realizar geométricamente quitando una cara triangular de un poliedro y extendiendo sus caras vecinas hasta el punto donde se encuentran, pero solo cuando ese punto de triple intersección de las tres caras vecinas está en el lado lejano. de la cara eliminada del poliedro. Cuando el punto de triple intersección no está en el lado más alejado de esta cara, una transformación proyectiva del poliedro es suficiente para moverlo al lado correcto. Por lo tanto, por inducción sobre el número de transformadas Δ-Y e Y-Δ necesarias para reducir un gráfico dado a K 4 , cada gráfico poliédrico se puede realizar como un poliedro. [5]
Un trabajo posterior de Epifanov reforzó la prueba de Steinitz de que cada gráfico poliédrico se puede reducir a K 4 mediante transformaciones Δ-Y e Y-Δ. Epifanov demostró que si se especifican dos vértices en un gráfico plano, entonces el gráfico se puede reducir a un solo borde entre esos terminales combinando transformadas Δ-Y e Y-Δ con reducciones en serie-paralelo . [13] La demostración de Epifanov era complicada y no constructiva, pero fue simplificada por Truemper usando métodos basados en grafos menores . Truemper observó que cada gráfico de cuadrícula se puede reducir mediante transformaciones Δ-Y y Y-Δ de esta manera, que esta reducibilidad se conserva mediante gráficos menores y que cada gráfico plano es un menor de un gráfico de cuadrícula. [14] Esta idea se puede utilizar para reemplazar el lema de Steinitz de que existe una secuencia de reducción. Tras esta sustitución, el resto de la prueba se puede realizar mediante inducción de la misma forma que la prueba original de Steinitz. [4] Para estas demostraciones, realizadas mediante cualquiera de las formas de encontrar secuencias de transformadas Δ-Y e Y-Δ, existen gráficas poliédricas que requieren un número de pasos no lineal. Más precisamente, a veces se necesitan pasos de Ω ( n 3/2 ), y el límite superior más conocido del número de pasos es incluso peor, O ( n 2 ). [15]
Una forma alternativa de prueba de inducción se basa en eliminar los bordes (y comprimir los vértices de grado dos que podrían realizarse con esta eliminación) o contraer los bordes y formar una parte menor del gráfico plano dado. Cualquier gráfico poliédrico puede reducirse a K 4 por un número lineal de estas operaciones, y nuevamente las operaciones pueden invertirse y las operaciones invertidas pueden realizarse geométricamente, dando una realización poliédrica del gráfico. Sin embargo, si bien 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. [dieciséis]
Levantamiento
Si se dibuja una gráfica en el plano con bordes de línea recta, entonces una tensión de equilibrio se define como una asignación de números reales distintos de cero (pesos) a los bordes, con la propiedad de que cada vértice está en la posición dada por la suma ponderada de su vecinos. De acuerdo con la correspondencia de Maxwell-Cremona, una tensión de equilibrio se puede elevar a una superficie tridimensional continua lineal a trozos de manera que los bordes que forman los límites entre las partes planas de la superficie se proyectan al dibujo dado. El peso y la longitud de cada borde determina la diferencia en pendientes de la superficie a cada lado del borde, y la condición de que cada vértice esté en equilibrio con sus vecinos es equivalente a la condición de que estas diferencias de pendiente provoquen que la superficie se encuentre con sí mismo correctamente en la vecindad del vértice. Los pesos positivos se traducen en ángulos diedros convexos entre dos caras de la superficie lineal por partes, y los pesos negativos se traducen en ángulos diedros cóncavos. A la inversa, toda superficie lineal continua a trozos proviene de una tensión de equilibrio de esta manera. Si se dibuja un gráfico plano finito y se le da un esfuerzo de equilibrio de tal manera que todos los bordes interiores del dibujo tienen pesos positivos y todos los bordes exteriores tienen pesos negativos, entonces al traducir este esfuerzo en una superficie tridimensional de esta manera, y luego reemplazando la superficie plana que representa el exterior de la gráfica 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. [17] [18]
La correspondencia Maxwell-Cremona se ha utilizado para obtener realizaciones poliédricas de gráficos poliédricos combinándola con un método de dibujo de gráfico plano de WT Tutte , la incrustación de Tutte . El método de Tutte comienza fijando una cara de un gráfico poliédrico en una posición convexa en el plano. Esta cara se convertirá en la cara exterior de un dibujo de un gráfico. El método continúa estableciendo un sistema de ecuaciones lineales en las coordenadas del vértice, según el cual cada vértice restante debe colocarse en el promedio de sus vecinos. Entonces, como mostró Tutte, este sistema de ecuaciones tendrá una solución única en la que cada cara del gráfico se dibuja como un polígono convexo. [19] El resultado es casi una tensión de equilibrio: si se asigna un peso uno a cada borde interior, entonces cada vértice interior del dibujo está en equilibrio. Sin embargo, no siempre es posible asignar números negativos a los bordes exteriores para que ellos también estén en equilibrio. Esta asignación siempre es posible cuando la cara exterior es un triángulo, por lo que este método se puede utilizar para realizar cualquier gráfico poliédrico que tenga una cara triangular. Si un gráfico poliédrico no contiene una cara triangular, su gráfico dual contiene un triángulo y también es poliédrico, por lo que uno puede realizar el dual de esta manera y luego realizar el gráfico original como el poliedro polar de la realización dual. [20] [21] También es posible realizar cualquier gráfico poliédrico directamente eligiendo la cara exterior para que sea cualquier cara con un máximo de cinco vértices (algo que existe en todos los gráficos poliédricos) y eligiendo con más cuidado la forma fija de esta cara en de tal manera que la incrustación de Tutte se pueda levantar, [22] o usando un método incremental en lugar del método de Tutte para encontrar un dibujo plano elevable que no tenga pesos iguales para todos los bordes interiores. [23]
Embalaje circular
De acuerdo con una variante del teorema de empaquetamiento de círculos , para cada grafo poliédrico y su grafo dual , existe un sistema de círculos en el plano o en cualquier esfera, que representan los vértices de ambos grafos, de modo que dos vértices adyacentes en el mismo grafo son representados por círculos tangentes , un vértice primario y doble que representan un vértice y una cara que se tocan entre sí están representados por círculos ortogonales, y todos los pares de círculos restantes son disjuntos. [24] A partir de tal representación en una esfera, se puede encontrar una realización poliédrica del gráfico dado como la intersección de una colección de medios espacios, uno para cada círculo que representa un vértice dual, con el límite del medio espacio que contiene el círculo. Alternativamente y de manera equivalente, se puede encontrar el mismo poliedro que el casco convexo de una colección de puntos (sus vértices), de modo que el horizonte visto al ver la esfera desde cualquier vértice es igual al círculo que corresponde a ese vértice. La esfera se convierte en la esfera media de la realización: cada borde del poliedro es tangente a él, en el punto donde se encuentran dos círculos primarios tangentes y dos círculos duales ortogonales a los círculos primarios y tangentes entre sí. [25]
Realizaciones con propiedades adicionales
Coordenadas enteras
Es posible probar una forma más sólida del teorema de Steinitz, que cualquier gráfico poliédrico puede realizarse mediante un poliedro convexo para el que todas las coordenadas de los vértices son números enteros. Por ejemplo, la prueba original basada en inducción de Steinitz se puede fortalecer de esta manera. Sin embargo, los números enteros que resultarían de esta construcción son doblemente exponenciales en el número de vértices del gráfico poliédrico dado. Escribir números de esta magnitud en notación binaria requeriría un número exponencial de bits. [26]
Investigadores posteriores han encontrado algoritmos de realización basados en levantamiento que usan solo O ( n ) bits por vértice. [22] [27] También es posible relajar el requisito de que las coordenadas sean números enteros y asignar coordenadas de tal manera que las coordenadas x de los vértices sean enteros distintos en el rango [0,2 n - 4] y las otras dos coordenadas son números reales en el rango [0,1], de modo que cada borde tiene una longitud de al menos uno mientras que el poliedro general tiene un volumen O ( n ). [28] Se sabe que algunos gráficos poliédricos se pueden realizar en cuadrículas de solo tamaño polinomial; en particular, esto es cierto para las pirámides (realizaciones de gráficos de ruedas ), prismas (realizaciones de gráficos de prismas ) y poliedros apilados (realizaciones de redes apolíneas ). [29]
Pendientes iguales
Un gráfico de Halin es un gráfico plano formado a partir de un árbol incrustado en un plano (sin vértices de grado dos) conectando las hojas del árbol en un ciclo . Cada gráfico de Halin se puede realizar mediante un poliedro en el que este ciclo forma una cara base horizontal, todas las demás caras se encuentran directamente encima de la cara base (como en los poliedros realizados mediante elevación) y todas las caras tienen la misma pendiente. De manera equivalente, el esqueleto recto de la cara base es combinatoriamente equivalente al árbol a partir del cual se formó el gráfico de Halin. La prueba de este resultado usa la inducción: cualquier árbol enraizado puede reducirse a un árbol más pequeño quitando las hojas de un nodo interno cuyos hijos son todas hojas, el gráfico 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 agregar cualquier número de hijos hoja al nodo del árbol cuyos hijos fueron eliminados. [30]
Especificar la forma de una cara
En cualquier poliedro que representa un gráfico poliédrico dado G , las caras de G son exactamente los ciclos de G que no separan a G en dos componentes: es decir, eliminar un ciclo facial de G deja el resto de G como un subgrafo conectado. Por lo tanto, la estructura combinatoria de las caras (pero no sus formas geométricas) se determina de forma única a partir de la estructura del gráfico. Otro fortalecimiento del teorema de Steinitz, por Barnette y Grünbaum, establece que para cualquier gráfico poliédrico, cualquier cara del gráfico y cualquier polígono convexo que represente esa cara, es posible encontrar una realización poliédrica de todo el gráfico que tiene la forma especificada para la cara designada. Esto está relacionado con un teorema de Tutte, que cualquier gráfico poliédrico se puede dibujar en el plano con todas las caras convexas y cualquier forma especificada para su cara exterior. Sin embargo, los dibujos de gráficos planos producidos por el método de Tutte no necesariamente se elevan a poliedros convexos. En cambio, Barnette y Grünbaum prueban este resultado usando un método inductivo [31] También es siempre posible, dado un gráfico poliédrico G y un ciclo arbitrario C en G , encontrar una realización para la cual C forma la silueta de la realización bajo proyección paralela. . [32]
Esferas tangentes
El teorema de empaquetamiento de círculos de Koebe –Andreev– Thurston se puede interpretar como que proporciona otro fortalecimiento del teorema de Steinitz, que cada grafo plano de 3 conexiones puede representarse como un poliedro convexo de tal manera que todas sus aristas sean tangentes a la misma esfera unitaria . [25] Al realizar una transformación de Möbius cuidadosamente elegida de un empaquetamiento circular antes de transformarlo en un poliedro, es posible encontrar una realización poliédrica que se dé cuenta de todas las simetrías del gráfico subyacente, en el sentido de que cada automorfismo del gráfico es una simetría de la realización poliédrica. [33] [34] Más generalmente, si G es un gráfico poliédrica y K es cualquier suavizar tridimensional cuerpo convexo , es posible encontrar una representación poliédrica de G en la que todos los bordes son tangentes a K . [35]
Métodos de embalaje Circle también se pueden utilizar para caracterizar las gráficas de poliedros que tienen una circumsphere o insphere . La caracterización involucra pesos de borde, restringidos por sistemas de desigualdades lineales. Estos pesos corresponden a los ángulos formados por círculos adyacentes en un sistema de círculos, formado por las intersecciones de las caras del poliedro con su circunsfera o los horizontes de los vértices del poliedro en su interior. [36] [37]
Resultados relacionados
En cualquier dimensión superior a tres, el problema algorítmico de Steinitz consiste en determinar si un entramado dado es el entramado de caras de un politopo convexo . Es completo para la teoría existencial de los reales por el teorema de universalidad de Richter-Gebert. [38] Sin embargo, debido a que un gráfico dado puede corresponder a más de un retículo de caras, es difícil extender este resultado de integridad al problema de reconocer los gráficos de 4-politopos, y la complejidad de este problema permanece abierta. [39]
Los investigadores también han encontrado caracterizaciones gráficas teóricas de los gráficos de ciertas clases especiales de poliedros tridimensionales no convexos [40] [41] y politopos convexos de cuatro dimensiones. [39] [42] [43] Sin embargo, en ambos casos, el problema general sigue sin resolverse. De hecho, incluso el problema de determinar qué gráficos completos son los gráficos de poliedros no convexos (distintos de K 4 para el tetraedro y K 7 para el poliedro de Császár ) permanece sin resolver. [44]
László Lovász ha mostrado una correspondencia entre representaciones poliédricas de gráficas y matrices realizando las invariantes gráficas de Colin de Verdière de las mismas gráficas. [45]
Referencias
- ^ Weisstein, Eric W. , "Gráfico poliédrico" , MathWorld
- ^ a b Grünbaum, Branko (2003), "13.1 Teorema de Steinitz", Politopos convexos , Textos de posgrado en matemáticas, 221 (2ª ed.), Springer-Verlag, págs. 235–244, ISBN 0-387-40409-0
- ^ Más técnicamente, este gráfico es el 1-esqueleto; ver Grünbaum (2003) , p. 138 y Ziegler (1995) , pág. 64.
- ^ a b Ziegler, Günter M. (1995), "Capítulo 4: Teorema de Steinitz para los 3-politopos", Conferencias sobre politopos , Textos de posgrado en matemáticas, 152 , Springer-Verlag, págs. 103-126, ISBN 0-387-94365-X
- ^ a b Steinitz, Ernst (1922), "Polyeder und Raumeinteilungen" , Encyclopädie der mathischen Wissenschaften , Band 3 (Geometries) , págs. 1-139,
Abgeschlossen am 31. Agosto de 1916
- ^ Zynel, Mariusz (1996), "El teorema de Steinitz y la dimensión de un espacio vectorial", Matemáticas formalizadas , 5 (8): 423–428, CiteSeerX 10.1.1.79.1707
- ^ Kirkpatrick, David ; Mishra, Bhubaneswar; Yap, Chee-Keng (1992), "Teoremas cuantitativos de Steinitz con aplicaciones a la comprensión de múltiples dedos ", Geometría discreta y computacional , 7 (1): 295–318, doi : 10.1007 / BF02187843
- ^ Rosenthal, Peter (1987), "El notable teorema de Lévy y Steinitz", The American Mathematical Monthly , 94 (4): 342–351, doi : 10.2307 / 2323094 , JSTOR 2323094
- ^ Banaszczyk, Wojciech (1991), "Capítulo 3.10 El teorema de Lévy-Steinitz", Subgrupos aditivos de espacios vectoriales topológicos , Lecture Notes in Mathematics, 1466 , Berlín: Springer-Verlag, pp. Viii + 178, ISBN 3-540-53917-4, MR 1119302
- ^ Kadets, VM; Kadets, MI (1991), "Capítulo 6 El teorema de Steinitz y B -convexidad", Reordenamientos de series en espacios de Banach , Traducciones de monografías matemáticas, 86 (Traducido por Harold H. McFaden del idioma ruso (Tartu) 1988 ed. ), Providence, RI: American Mathematical Society, págs. Iv + 123, ISBN 0-8218-4546-2, MR 1108619
- ^ Kadets, Mikhail I .; Kadets, Vladimir M. (1997), "Capítulo 2.1 Teorema de Steinitz sobre el rango de suma de una serie, Capítulo 7 El teorema de Steinitz y la convexidad B ", Series en espacios de Banach: Convergencia condicional e incondicional , Teoría del operador: avances y aplicaciones, 94 (Traducido por Andrei Iacob de la edición en ruso), Basilea: Birkhäuser Verlag, págs. Viii + 156, ISBN 3-7643-5401-1, MR 1442255
- ^ Balinski, ML (1961), "Sobre la estructura gráfica de poliedros convexos en n- espacio" , Pacific Journal of Mathematics , 11 (2): 431–434, doi : 10.2140 / pjm.1961.11.431 , MR 0126765
- ^ Epifanov, GV (1966), "Reducción de un gráfico plano a un borde mediante transformaciones estrella-triángulo", Doklady Akademii Nauk SSSR , 166 : 19-22, MR 0201337
- ^ Truemper, K. (1989), "Sobre la reducción delta-estrella para gráficos planos", Journal of Graph Theory , 13 (2): 141–148, doi : 10.1002 / jgt.3190130202 , MR 0994737
- ^ Chang, Hsien-Chih; Cossarini, Marcos; Erickson, Jeff (2019), "Límites inferiores para reducción eléctrica en superficies", en Barequet, Gill; Wang, Yusu (eds.), 35th International Symposium on Computational Geometry (SoCG 2019) , Leibniz International Proceedings in Informatics (LIPIcs), 129 , Dagstuhl, Alemania: Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, págs. 25: 1–25 : 16, arXiv : 1707.04683 , doi : 10.4230 / LIPIcs.SoCG.2019.25 , ISBN 978-3-95977-104-7, MR 3968611
- ^ Barnette, David W .; Grünbaum, Branko (1969), "Sobre el teorema de Steinitz sobre los 3-politopos convexos y sobre algunas propiedades de los gráficos planos", The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Michigan, 1968) , Springer, págs. 27–40, MR 0250916
- ^ Maxwell, J. Clerk (1864), "Sobre figuras recíprocas y diagramas de fuerzas", Revista filosófica , cuarta serie, 27 : 250-261
- ^ Whiteley, Walter (1982), "Movimientos y tensiones de poliedros proyectados", Topología estructural , 7 : 13–38, MR 0721947
- ^ Tutte, WT (1963), "Cómo dibujar un gráfico", Proceedings of the London Mathematical Society , 13 : 743–767, doi : 10.1112 / plms / s3-13.1.743 , MR 0158387
- ^ Onn, Shmuel; Sturmfels, Bernd (1994), "Un teorema cuantitativo de Steinitz", Beiträge zur Algebra und Geometrie , 35 (1): 125-129, MR 1287206
- ^ Eades, Peter ; Garvan, Patrick (1996), "Dibujar gráficas planas acentuadas en tres dimensiones", Dibujo de gráficas (GD '95) , Lecture Notes in Computer Science , 1027 , Springer, págs. 212-223, doi : 10.1007 / bfb0021805
- ^ a b Ribó Mor, Ares; Rote, Günter; Schulz, André (2011), "Small Grid Embeddings of 3-Polytopes", Geometría discreta y computacional , 45 (1): 65–87, arXiv : 0908.0488 , doi : 10.1007 / s00454-010-9301-0 , S2CID 10141034
- ^ Chrobak, Marek; Goodrich, Michael T .; Tamassia, Roberto (1996), "Dibujos convexos de gráficos en dos y tres dimensiones", Actas del 12 ° Simposio ACM sobre geometría computacional (SoCG '96) , ACM, págs. 319–328, doi : 10.1145 / 237218.237401 , S2CID 1015103
- ^ Brightwell, Graham R .; Scheinerman, Edward R. (1993), "Representaciones de gráficos planos", SIAM Journal on Discrete Mathematics , 6 (2): 214-229, doi : 10.1137 / 0406017
- ^ a b Ziegler, Günter M. (2007), " Politopos convexos: construcciones extremas y formas de vectores f . Sección 1.3: Teorema de Steinitz a través de empaquetaduras circulares", en Miller, Ezra; Reiner, Victor; Sturmfels, Bernd (eds.), Combinatoria geométrica , IAS / Park City Mathematics Series, 13 , American Mathematical Society , págs. 628–642, ISBN 978-0-8218-3736-8
- ^ Venkatasubramanian, Suresh (2006), gráficas planas y teorema de Steinitz
- ^ Buchin, Kevin; Schulz, André (2010), "Sobre el número de árboles de expansión que puede tener un gráfico plano", Algoritmos - 18º Simposio Europeo Anual (ESA 2010) , Lecture Notes in Computer Science, 6346 , Springer-Verlag, pp. 110-121, Código bibliográfico : 2010LNCS.6346 ..... D , doi : 10.1007 / 978-3-642-15775-2 , ISBN 978-3-642-15774-5
- ^ Schulz, André (2011), "Dibujo de 3 politopos con buena resolución de vértice" (PDF) , Journal of Graph Algorithms and Applications , 15 (1): 33–52, doi : 10.7155 / jgaa.00216
- ^ Demaine, Erik D .; Schulz, André (2017), "Incorporación de politopos apilados en una cuadrícula de tamaño polinómico", Geometría discreta y computacional , 57 (4): 782–809, arXiv : 1403.7980 , doi : 10.1007 / s00454-017-9887-6 , MR 3639604
- ^ Aichholzer, Oswin; Cheng, Howard; Devadoss, Satyan L .; Hackl, Thomas; Huber, Stefan; Li, Brian; Risteski, Andrej (2012), "¿Qué hace que un árbol sea un esqueleto recto?" (PDF) , Actas de la 24a Conferencia Canadiense sobre Geometría Computacional (CCCG'12)
- ^ Barnette, David W .; Grünbaum, Branko (1970), "Preasignación de la forma de una cara" , Pacific Journal of Mathematics , 32 (2): 299–306, doi : 10.2140 / pjm.1970.32.299 , MR 0259744
- ^ Barnette, David W. (1970), "Projections of 3-polytopes", Israel Journal of Mathematics , 8 (3): 304–308, doi : 10.1007 / BF02771563 , S2CID 120791830
- ^ Hart, George W. (1997), "Calculating canonical polyhedra" , Mathematica in Education and Research , 6 (3): 5–10
- ^ Berna, Marshall; Eppstein, David (2001), "Transformaciones óptimas de Möbius para visualización y mallado de información", Proc. 7th Worksh. Algoritmos y estructuras de datos (WADS 2001) , Lect. Notas Comp. Sci., 2125 , Springer, págs. 14-25, arXiv : cs / 0101006 , doi : 10.1007 / 3-540-44634-6_3 , S2CID 3266233
- ^ Schramm, Oded (1992), "How to jaula an egg", Inventiones Mathematicae , 107 (3): 543–560, Bibcode : 1992InMat.107..543S , doi : 10.1007 / BF01231901 , MR 1150601 , S2CID 189830473
- ^ Rivin, Igor (1996), "Una caracterización de poliedros ideales en 3 espacios hiperbólicos", Annals of Mathematics , Second Series, 143 (1): 51-70, doi : 10.2307 / 2118652 , JSTOR 2118652 , MR 1370757
- ^ Dillencourt, Michael B .; Smith, Warren D. (1996), "Condiciones gráficas teóricas para la inscribibilidad y la realizabilidad de Delaunay" , Matemáticas discretas , 161 (1-3): 63-77, doi : 10.1016 / 0012-365X (95) 00276-3 , MR 1420521
- ^ Richter-Gebert, Jürgen (1996), Espacios de realización de politopos , Lecture Notes in Mathematics, 1643 , Springer-Verlag, ISBN 978-3-540-62084-6
- ^ a b Eppstein, David (2020), "Treetopes and their graphs", Geometría discreta y computacional , 64 (2): 259–289, arXiv : 1510.03152 , doi : 10.1007 / s00454-020-00177-0 , MR 4131546
- ^ Hong, Seok-Hee; Nagamochi, Hiroshi (2011), "Extendiendo el teorema de Steinitz a poliedros en forma de estrella ascendente y poliedros esféricos", Algorithmica , 61 (4): 1022-1076, doi : 10.1007 / s00453-011-9570-x , MR 2852056 , S2CID 12622357
- ^ Eppstein, David ; Mumford, Elena (2014), "Teoremas de Steinitz para poliedros ortogonales simples", Journal of Computational Geometry , 5 (1): 179–244, MR 3259910
- ^ Ciego, Roswitha; Mani-Levitska, Peter (1987), "Rompecabezas e isomorfismos de politopos", Aequationes Mathematicae , 34 (2–3): 287–297, doi : 10.1007 / BF01830678 , MR 0921106 , S2CID 120222616
- ^ Kalai, Gil (1988), "Una manera simple de distinguir un politopo simple de su gráfico", Journal of Combinatorial Theory , Serie A, 49 (2): 381–383, doi : 10.1016 / 0097-3165 (88) 90064- 7 , MR 0964396
- ^ Ziegler, Günter M. (2008), "Superficies poliédricas de alto género", Geometría diferencial discreta , Seminarios de Oberwolfach, 38 , Springer, págs. 191-213, arXiv : math / 0412093 , doi : 10.1007 / 978-3-7643- 8621-4_10 , ISBN 978-3-7643-8620-7, MR 2405667 , S2CID 15911143
- ^ Lovász, László (2001), "Representaciones de Steinitz de poliedros y el número de Colin de Verdière", Journal of Combinatorial Theory , Serie B, 82 (2): 223-236, doi : 10.1006 / jctb.2000.2027 , MR 1842113