Teorema de Steinitz

Teorema de Steinitz (Redirecionado do teorema de Steinitz) Ir para a navegação Ir para a pesquisa Este artigo é sobre o teorema dos grafos de poliedros. Para outros usos, veja o teorema de Steinitz (desambiguação).

Em combinatória poliédrica, um ramo da matemática, O teorema de Steinitz é uma caracterização dos grafos não direcionados formados pelas arestas e vértices de poliedros convexos tridimensionais: eles são exatamente os grafos planares conectados por 3 vértices. Aquilo é, todo poliedro convexo forma um grafo planar triconectado, e todo grafo plano triconectado pode ser representado como o grafo de um poliedro convexo. Por esta razão, os grafos planos triconectados também são conhecidos como grafos poliédricos.[1] Este resultado fornece um teorema de classificação para os poliedros convexos tridimensionais, algo que não é conhecido em dimensões superiores.[2] Ele fornece uma descrição completa e puramente combinatória dos gráficos desses poliedros, permitindo outros resultados sobre eles, como o teorema de Eberhard sobre a realização de poliedros com determinados tipos de faces, ser provado mais facilmente, sem referência à geometria dessas formas.[3] Adicionalmente, foi aplicado no desenho gráfico, como forma de construir visualizações tridimensionais de gráficos abstratos.[4] Branko Grünbaum chamou este teorema "o resultado mais importante e mais profundo conhecido em 3-politopos."[5] O teorema aparece em 1922 publicação de Ernst Steinitz,[6] depois de quem é nomeado. Pode ser provado por indução matemática (como Steinitz fez), encontrando o estado de energia mínima de um sistema de mola bidimensional e elevando o resultado em três dimensões, ou usando o teorema do empacotamento circular. Várias extensões do teorema são conhecidas, em que o poliedro que realiza um dado grafo tem restrições adicionais; por exemplo, todo gráfico poliédrico é o gráfico de um poliedro convexo com coordenadas inteiras, ou o gráfico de um poliedro convexo cujas arestas são tangentes a uma esfera média comum.

Conteúdo 1 Definições e declaração do teorema 2 Provas 2.1 Indução 2.2 Elevação 2.3 Embalagem circular 3 Realizações com propriedades adicionais 3.1 Coordenadas inteiras 3.2 Inclinações iguais 3.3 Especificando a forma de um rosto 3.4 Esferas tangentes 4 Resultados relacionados 5 História 6 Referências Definições e enunciados do teorema Iluminar o esqueleto de um poliedro convexo a partir de uma fonte de luz próxima a uma de suas faces faz com que suas sombras formem um diagrama de Schlegel planar.

Um grafo não direcionado é um sistema de vértices e arestas, cada aresta conectando dois dos vértices. De qualquer poliedro pode-se formar um grafo, deixando os vértices do grafo corresponderem aos vértices do poliedro e conectando quaisquer dois vértices do grafo por uma aresta sempre que os dois vértices do poliedro correspondentes forem as extremidades de uma aresta do poliedro. Este gráfico é conhecido como o esqueleto do poliedro.[7] Um grafo é planar se puder ser desenhado com seus vértices como pontos no plano euclidiano, e suas arestas como curvas que conectam esses pontos, tal que duas curvas de aresta não se cruzem e tal que o ponto que representa um vértice esteja na curva que representa uma aresta somente quando o vértice for um ponto final da aresta. Pelo teorema de Fary, todo desenho plano pode ser endireitado para que as curvas que representam as arestas sejam segmentos de linha. Um grafo é triconectado se tiver mais de três vértices e, após a remoção de quaisquer dois de seus vértices, qualquer outro par de vértices permanece conectado por um caminho. O teorema de Steinitz afirma que essas duas condições são necessárias e suficientes para caracterizar os esqueletos de poliedros convexos tridimensionais: um determinado gráfico {estilo de exibição G} é o gráfico de um poliedro tridimensional convexo, se e apenas se {estilo de exibição G} é planar e conectado a 3 vértices.[5][8] Demonstrações Ilustração da prova do teorema de Balinski, mostrando o conjunto zero de uma função linear (azul) passando por dois vértices dados (amarelo) e os caminhos do método simplex conectando o grafo restante (verde) Uma direção do teorema de Steinitz (a direção mais fácil de provar) afirma que o gráfico de todo poliedro convexo é planar e triconectado. Como mostrado na ilustração, a planaridade pode ser mostrada usando um diagrama de Schlegel: se colocarmos uma fonte de luz perto de uma face do poliedro, e um avião do outro lado, as sombras das arestas do poliedro formarão um gráfico planar, embutidos de tal forma que as bordas são segmentos de linha reta. A 3-conectividade de um grafo poliédrico é um caso especial do teorema de Balinski que o grafo de qualquer {estilo de exibição k} -politopo convexo dimensional é {estilo de exibição k} -conectado. A conectividade do grafo de um politopo, depois de remover qualquer {estilo de exibição k-1} de seus vértices, pode ser provado escolhendo mais um vértice {estilo de exibição v} , encontrar uma função linear que é zero no conjunto resultante de {estilo de exibição k} vértices, e seguindo os caminhos gerados pelo método simplex para conectar cada vértice a um dos dois vértices extremos da função linear, com o vértice escolhido {estilo de exibição v} conectado a ambos.[9] O outro, mais difícil, direção do teorema de Steinitz afirma que todo grafo planar 3-conectado é o gráfico de um poliedro convexo. Existem três abordagens padrão para esta parte: provas por indução, levantando incorporações de Tutte bidimensionais em três dimensões usando a correspondência de Maxwell-Cremona, e métodos usando o teorema do empacotamento circular para gerar um poliedro canônico.

Induction Δ-Y and Y-Δ transforms of a polyhedron Although Steinitz's original proof was not expressed in terms of graph theory, pode ser reescrito nesses termos, e envolve encontrar uma sequência de transformadas Δ-Y e Y-Δ que reduzam qualquer gráfico planar triconectado a {estilo de exibição K_{4}} , o gráfico do tetraedro. Uma transformação Y-Δ remove um vértice de grau três de um grafo, adicionando arestas entre todos os seus antigos vizinhos se essas arestas ainda não existissem; a transformação inversa, uma transformada Δ-Y, remove as arestas de um triângulo de um grafo e as substitui por um novo vértice de grau três adjacente aos mesmos três vértices. Uma vez que tal sequência é encontrada, ele pode ser revertido e convertido em operações geométricas que constroem o poliedro desejado passo a passo a partir de um tetraedro. Cada transformação Y-Δ na sequência inversa pode ser executada geometricamente cortando um vértice de grau três de um poliedro. Uma transformada Δ-Y na sequência inversa pode ser realizada geometricamente removendo uma face triangular de um poliedro e estendendo suas faces vizinhas até o ponto onde elas se encontram., mas somente quando esse ponto de interseção tripla das três faces vizinhas estiver no lado mais distante da face removida do poliedro. Quando o ponto de interseção tripla não está do outro lado desta face, uma transformação projetiva do poliedro é suficiente para movê-lo para o lado correto. Portanto, por indução no número de transformações Δ-Y e Y-Δ necessárias para reduzir um dado gráfico a {estilo de exibição K_{4}} , todo grafo poliédrico pode ser realizado como um poliedro.[5] Um trabalho posterior de Epifanov reforçou a prova de Steinitz de que todo grafo poliédrico pode ser reduzido a {estilo de exibição K_{4}} pelas transformadas Δ-Y e Y-Δ. Epifanov provou que se dois vértices são especificados em um grafo planar, então o gráfico pode ser reduzido a uma única aresta entre esses terminais combinando as transformadas Δ-Y e Y-Δ com reduções em série-paralelo.[10] A prova de Epifanov foi complicada e não construtiva, mas foi simplificado por Truemper usando métodos baseados em gráficos menores. Truemper observou que todo gráfico de grade é redutível por transformações Δ-Y e Y-Δ dessa maneira, que esta redutibilidade é preservada por gráficos menores, e que todo grafo planar é menor de um grafo de grade.[11] Esta ideia pode ser usada para substituir o lema de Steinitz de que existe uma sequência de redução. Após esta substituição, o resto da prova pode ser realizada usando indução da mesma forma que a prova original de Steinitz.[8] Para essas provas, realizado usando qualquer uma das maneiras de encontrar sequências de transformadas Δ-Y e Y-Δ, existem gráficos poliédricos que requerem um número não linear de passos. Mais precisamente, infinitos grafos requerem um número de passos pelo menos proporcional a {estilo de exibição n^{3/2}} , Onde {estilo de exibição m} é o número de vértices no gráfico, e o limite superior mais conhecido no número de passos que são suficientes é maior, proporcional a {estilo de exibição n^{2}} .[12] Uma forma alternativa de prova por indução é baseada na remoção de arestas (e comprimindo os vértices de grau dois que podem ser deixados após essa remoção) ou contraindo arestas e formando um menor do grafo planar dado. Qualquer gráfico poliédrico pode ser reduzido a {estilo de exibição K_{4}} por um número linear dessas operações, e novamente as operações podem ser revertidas e as operações invertidas executadas geometricamente, dando uma realização poliédrica do gráfico. No entanto, enquanto é mais simples provar que existe uma sequência de redução para este tipo de argumento, e as sequências de redução são mais curtas, os passos geométricos necessários para reverter a sequência são mais complicados.[13] Levantando a tensão de equilíbrio no gráfico de um cubo Um tronco levantando o desenho estressado (com as mesmas posições 2d) into 3d If a graph is drawn in the plane with straight line edges, então uma tensão de equilíbrio é definida como uma atribuição de números reais diferentes de zero (pesos) para as bordas, com a propriedade de que cada vértice está na posição dada pela média ponderada de seus vizinhos. De acordo com a correspondência Maxwell-Cremona, uma tensão de equilíbrio pode ser levantada para uma superfície tridimensional contínua linear por partes, de modo que as bordas que formam os limites entre as partes planas da superfície se projetem para o desenho dado. O peso e o comprimento de cada aresta determinam a diferença nas inclinações da superfície em ambos os lados da aresta, e a condição de que cada vértice esteja em equilíbrio com seus vizinhos é equivalente à condição de que essas diferenças de inclinação façam com que a superfície se encontre corretamente na vizinhança do vértice. Pesos positivos se traduzem em ângulos diedros convexos entre duas faces da superfície linear por partes, e pesos negativos se traduzem em ângulos diedros côncavos. Por outro lado, toda superfície linear contínua por partes vem de uma tensão de equilíbrio dessa maneira. Se um gráfico plano finito é desenhado e recebe uma tensão de equilíbrio de tal forma que todas as arestas internas do desenho têm pesos positivos, e todas as arestas exteriores têm pesos negativos, então, traduzindo essa tensão em uma superfície tridimensional dessa maneira, e, em seguida, substituindo a superfície plana que representa o exterior do gráfico por seu complemento no mesmo plano, obtém-se um poliedro convexo, com a propriedade adicional de que sua projeção perpendicular no plano não tem cruzamentos.[14][15] A correspondência de Maxwell-Cremona foi usada para obter realizações poliédricas de gráficos poliédricos combinando-a com um método de desenho de gráfico plano de W. T. Tudo, a incorporação de Tutte. O método de Tutte começa fixando uma face de um gráfico poliédrico em posição convexa no plano. Esta face se tornará a face externa de um desenho de um gráfico. O método continua configurando um sistema de equações lineares nas coordenadas do vértice, segundo o qual cada vértice restante deve ser colocado na média de seus vizinhos. Então, como Tutte mostrou, este sistema de equações terá uma solução única na qual cada face do gráfico é desenhada como um polígono convexo.[16] Intuitivamente, esta solução descreve o padrão que seria obtido substituindo as arestas internas do gráfico por molas ideais e deixando-as estabilizar em seu estado de energia mínima.[17] O resultado é quase uma tensão de equilíbrio: se atribui peso um a cada aresta interior, então cada vértice interior do desenho está em equilíbrio. No entanto, nem sempre é possível atribuir números negativos às arestas externas para que elas, também, estão em equilíbrio. Tal atribuição é sempre possível quando a face externa é um triângulo, e assim este método pode ser usado para realizar qualquer grafo poliédrico que tenha uma face triangular. Se um gráfico poliédrico não contém uma face triangular, seu gráfico dual contém um triângulo e também é poliédrico, então pode-se perceber o dual desta maneira e então perceber o gráfico original como o poliedro polar da realização dual.[4][18] Um método alternativo para realizar poliedros usando levantamentos evita a dualidade ao escolher qualquer face com no máximo cinco vértices como face externa. Todo grafo poliédrico tem tal face, e escolhendo a forma fixa desse rosto com mais cuidado, a incorporação de Tutte do resto do gráfico pode ser levantada.[19] Embalagem circular Um poliedro realizado a partir de uma embalagem circular na esfera média azul. Cada vértice do poliedro é representado no empacotamento pelo seu círculo do horizonte (vermelho). Cada face é representada pelo círculo formado por sua interseção com a esfera.

De acordo com uma variante do teorema do empacotamento circular, para cada gráfico poliédrico, existe um sistema de círculos no plano ou em qualquer esfera, representando os vértices e faces do gráfico, de modo a: cada dois vértices adjacentes do gráfico são representados por círculos tangentes, cada duas faces adjacentes do gráfico são representadas por um círculo tangente, cada par de um vértice e uma face que ele toca são representados por círculos que se cruzam em ângulo reto, e todos os outros pares de círculos são separados um do outro.[20] O mesmo sistema de círculos forma uma representação do grafo dual trocando os papéis dos círculos que representam os vértices, e círculos que representam rostos. De qualquer representação em uma esfera, embutido no espaço euclidiano tridimensional, pode-se formar um poliedro convexo que é combinatorialmente equivalente ao grafo dado, como uma interseção de semi-espaços cujos limites passam pelos círculos faciais. De cada vértice deste poliedro, o horizonte na esfera, visto desse vértice, é o círculo que o representa. Esta propriedade de horizonte determina a posição tridimensional de cada vértice, e o poliedro pode ser equivalentemente definido como o casco convexo dos vértices, posicionado desta forma. A esfera torna-se a esfera média da realização: cada aresta do poliedro é tangente à esfera, em um ponto onde dois círculos de vértices tangentes cruzam dois círculos de faces tangentes.[21] Realizations with additional properties Integer coordinates It is possible to prove a stronger form of Steinitz's theorem, que qualquer grafo poliédrico pode ser realizado por um poliedro convexo cujas coordenadas são inteiras.[22] Por exemplo, A prova original baseada em indução de Steinitz pode ser reforçada desta forma. No entanto, os inteiros que resultariam da construção de Steinitz são duplamente exponenciais no número de vértices do grafo poliédrico dado. Escrever números dessa magnitude em notação binária exigiria um número exponencial de bits.[18] Geometricamente, isso significa que algumas características do poliedro podem ter tamanho duas vezes exponencialmente maior do que outras, tornando as realizações derivadas deste método problemáticas para aplicações em desenho gráfico.[4] Pesquisadores subsequentes descobriram algoritmos de realização baseados em levantamento que usam apenas um número linear de bits por vértice.[19][23] Também é possível relaxar o requisito de que as coordenadas sejam números inteiros, e atribuir coordenadas de tal forma que o {estilo de exibição x} -coordenadas dos vértices são inteiros distintos no intervalo de 0 para {estilo de exibição 2n-4} e as outras duas coordenadas são números reais no intervalo unitário, de modo que cada aresta tenha comprimento de pelo menos um, enquanto o poliedro total tem volume linear.[24][25] Alguns grafos poliédricos são conhecidos por serem realizáveis ​​em grades apenas de tamanho polinomial; em particular, isso é verdade para as pirâmides (realizações de gráficos de roda), prismas (realizações de gráficos de prisma), e poliedros empilhados (realizações de redes apolíneas).[26] Outra maneira de afirmar a existência de realizações inteiras é que todo poliedro convexo tridimensional tem um poliedro inteiro combinatorialmente equivalente.[22] Por exemplo, o dodecaedro regular não é um poliedro inteiro, por causa de suas faces regulares do pentágono, mas pode ser realizado como um piritoedro inteiro equivalente.[19] Isso nem sempre é possível em dimensões mais altas, onde existem politopos (como os construídos a partir da configuração de Perles) que não têm equivalente inteiro.[27] Equal slopes A Halin graph is a special case of a polyhedral graph, formado a partir de uma árvore planar-embebida (sem vértices de grau dois) conectando as folhas da árvore em um ciclo. Para gráficos de Halin, pode-se escolher realizações poliédricas de um tipo especial: o ciclo externo forma uma face de base convexa horizontal, e todas as outras faces estão diretamente acima da face base (como no poliedro realizado através do levantamento), com todas essas faces superiores tendo a mesma inclinação. Superfícies poliédricas com faces de inclinação igual sobre qualquer polígono de base (não necessariamente convexo) pode ser construído a partir do esqueleto reto do polígono, e uma maneira equivalente de descrever essa percepção é que a projeção bidimensional da árvore na face da base forma seu esqueleto reto.. A prova deste resultado usa indução: qualquer árvore enraizada pode ser reduzida a uma árvore menor removendo as folhas de um nó interno cujos filhos são todos folhas, o gráfico de Halin formado a partir da árvore menor tem uma realização pela hipótese de indução, e é possível modificar essa realização para adicionar qualquer número de filhos folha ao nó da árvore cujos filhos foram removidos.[28] Specifying the shape of a face In any polyhedron that represents a given polyhedral graph {estilo de exibição G} , os rostos de {estilo de exibição G} são exatamente os ciclos em {estilo de exibição G} que não separa {estilo de exibição G} em dois componentes: isso é, remover um ciclo facial de {estilo de exibição G} deixa o resto {estilo de exibição G} como um subgrafo conectado. Esses ciclos são chamados de ciclos periféricos. Desta forma, a estrutura combinatória das faces (mas não suas formas geométricas) é determinado exclusivamente a partir da estrutura do gráfico. Outro reforço do teorema de Steinitz, por Barnette e Grünbaum, afirma que para qualquer grafo poliédrico, qualquer face do gráfico, e qualquer polígono convexo representando essa face, é possível encontrar uma realização poliédrica de todo o gráfico que tenha a forma especificada para a face designada. Isso está relacionado a um teorema de Tutte, que qualquer gráfico poliédrico pode ser desenhado no plano com todas as faces convexas e qualquer forma especificada para sua face externa. No entanto, os desenhos de gráficos planos produzidos pelo método de Tutte não necessariamente se elevam para poliedros convexos. Em vez de, Barnette e Grünbaum provam este resultado usando um método indutivo.[29] Também é sempre possível, dado um gráfico poliédrico {estilo de exibição G} e um ciclo arbitrário {estilo de exibição C} dentro {estilo de exibição G} , encontrar uma realização para a qual {estilo de exibição C} forma a silhueta da realização sob projeção paralela.[30] Tangent spheres The realization of polyhedra using the circle packing theorem provides another strengthening of Steinitz's theorem: todo grafo plano triconectado pode ser representado como um poliedro convexo de tal forma que todas as suas arestas são tangentes à mesma esfera unitária, a esfera média do poliedro.[21] Ao realizar uma transformação de Möbius cuidadosamente escolhida de um empacotamento circular antes de transformá-lo em um poliedro, é possível encontrar uma realização poliédrica que realiza todas as simetrias do grafo subjacente, no sentido de que todo automorfismo de grafo é uma simetria da realização poliédrica.[31][32] De forma geral, E se {estilo de exibição G} é um grafo poliédrico e {estilo de exibição K} é qualquer corpo convexo tridimensional liso, é possível encontrar uma representação poliédrica de {estilo de exibição G} em que todas as arestas são tangentes {estilo de exibição K} .[33] Os métodos de empacotamento circular também podem ser usados ​​para caracterizar os grafos de poliedros que possuem uma circunsfera em todos os seus vértices, ou uma esfera tangente a todas as suas faces. (Os poliedros com uma circunsfera também são significativos na geometria hiperbólica como o poliedro ideal.) Em ambos os casos, a existência de uma esfera é equivalente à solubilidade de um sistema de desigualdades lineares em variáveis ​​reais positivas associadas a cada aresta do gráfico. No caso da esfera, essas variáveis ​​devem somar exatamente uma em cada ciclo de face do gráfico, e a mais de um em cada ciclo não presencial. Duplamente, para a circunsfera, as variáveis ​​devem somar um em cada vértice, e mais de um em cada corte com dois ou mais vértices em cada lado do corte. Embora possa haver exponencialmente muitas desigualdades lineares para satisfazer, uma solução (se existe um) pode ser encontrado em tempo polinomial usando o método elipsóide. Os valores das variáveis ​​de uma solução determinam os ângulos entre pares de círculos em um empacotamento circular cujo poliedro correspondente tem a relação desejada com sua esfera.[34][35] Resultados relacionados Os gráficos de poliedros não convexos tridimensionais podem não estar conectados (deixei), e mesmo para poliedros topologicamente esféricos cujas faces são polígonos simples, esses gráficos podem não ser triconectados (certo).[36] Em qualquer dimensão superior a três, o problema algorítmico de Steinitz consiste em determinar se um dado retículo é o retículo de face de um politopo convexo. É improvável que tenha complexidade de tempo polinomial, como é NP-difícil e mais fortemente completo para a teoria existencial dos reais, mesmo para politopos de quatro dimensões, pelo teorema da universalidade de Richter-Gebert.[37] Aqui, a teoria existencial dos reais é uma classe de problemas computacionais que podem ser formulados em termos de encontrar variáveis ​​reais que satisfaçam um determinado sistema de equações polinomiais e desigualdades. Para o problema algorítmico de Steinitz, as variáveis ​​de tal problema podem ser as coordenadas do vértice de um politopo, e as equações e desigualdades podem ser usadas para especificar a planicidade de cada face na rede de face dada e a convexidade de cada ângulo entre as faces. Completude significa que todos os outros problemas desta classe podem ser transformados em uma instância equivalente do problema algorítmico de Steinitz, em tempo polinomial. A existência de tal transformação implica que, se o problema algorítmico de Steinitz tem uma solução em tempo polinomial, então o mesmo acontece com todos os problemas na teoria existencial dos reais, e todos os problemas em NP.[38] No entanto, porque um determinado grafo pode corresponder a mais de uma rede de faces, é difícil estender este resultado de completude para o problema de reconhecer os gráficos de 4-politopos. Determinar a complexidade computacional deste problema de reconhecimento de grafos permanece em aberto.[39] Os pesquisadores também encontraram caracterizações teóricas dos gráficos dos gráficos de certas classes especiais de poliedros não convexos tridimensionais[36][40] e politopos convexos quadridimensionais.[39][41][42] No entanto, em ambos os casos, o problema geral permanece sem solução. De fato, até mesmo o problema de determinar quais grafos completos são os grafos de poliedros não convexos (outro que não seja {estilo de exibição K_{4}} para o tetraedro e {estilo de exibição K_{7}} para o poliedro do imperador) permanece sem solução.[43] O teorema de Eberhard caracteriza parcialmente os multiconjuntos de polígonos que podem ser combinados para formar as faces de um poliedro convexo. Pode ser provado formando um grafo planar de 3 conexos com o conjunto dado de faces de polígonos, e então aplicando o teorema de Steinitz para encontrar uma realização poliédrica desse grafo.[3] László Lovász mostrou uma correspondência entre representações poliédricas de grafos e matrizes realizando os invariantes de grafos de Colin de Verdière dos mesmos grafos. O invariante de Colin de Verdière é o corank máximo de uma matriz de adjacência ponderada do gráfico, sob algumas condições adicionais que são irrelevantes para gráficos poliédricos. São matrizes quadradas simétricas indexadas pelos vértices, com o peso do vértice {estilo de exibição eu} no coeficiente diagonal {estilo de exibição M_{eu,eu}} e com o peso da borda {estilo de exibição eu,j} nos coeficientes fora da diagonal {estilo de exibição M_{eu,j}} e {estilo de exibição M_{j,eu}} . Quando os vértices {estilo de exibição eu} e {estilo de exibição j} não são adjacentes, o coeficiente {estilo de exibição M_{eu,j}} é necessário ser zero. Esta invariante é no máximo três se e somente se o grafo for um grafo planar. Como mostra Lovász, quando o gráfico é poliédrico, uma representação dele como um poliedro pode ser obtida encontrando uma matriz de adjacência ponderada de corank três, encontrar três vetores formando uma base para seu espaço nulo, usando os coeficientes desses vetores como coordenadas para os vértices de um poliedro, e dimensionar esses vértices adequadamente.[44] History The history of Steinitz's theorem is described by Grünbaum (2007),[45] que observa sua primeira aparição de forma enigmática em uma publicação de Ernst Steinitz, originalmente escrito em 1916.[6] Steinitz forneceu mais detalhes em notas de aula posteriores, publicado depois de sua 1928 morte. Embora os tratamentos modernos do teorema de Steinitz o declarem como uma caracterização grafo-teórica de poliedros, Steinitz não usou a linguagem dos gráficos.[45] A formulação da teoria dos grafos do teorema foi introduzida no início dos anos 1960 por Branko Grünbaum e Theodore Motzkin, com sua prova também convertida em teoria dos grafos na teoria de Grünbaum 1967 texto politopos convexos.[45] O trabalho de Epifanov em Δ-Y e Y-Δ transforma, reforçando a prova de Steinitz, foi motivada por outros problemas que não a caracterização de poliedros. Truemper (1989) credita a Grünbaum a observação da relevância deste trabalho para o teorema de Steinitz.[11] A correspondência de Maxwell-Cremona entre diagramas de tensão e levantamentos poliédricos foi desenvolvida em uma série de artigos de James Clerk Maxwell de 1864 para 1870, baseado em trabalhos anteriores de Pierre Varignon, William Rankine, e outros, e foi popularizado no final do século 19 por Luigi Cremona.[46] The observation that this correspondence can be used with the Tutte embedding to prove Steinitz's theorem comes from Eades & Garvan (1995).[4] O teorema do empacotamento circular foi provado por Paul Koebe em 1936[47][48] e (independentemente) tchau. M. Andreev em 1970;[48][49] foi popularizado em meados da década de 1980 por William Thurston, quem (apesar de citar Koebe e Andreev) é frequentemente creditado como um de seus descobridores.[48] A versão do teorema de Andreev já foi formulada como uma caracterização do tipo Steinitz para certos poliedros no espaço hiperbólico,[49] e o uso de embalagem circular para realizar poliedros com esferas médias vem do trabalho de Thurston.[50] O problema de caracterizar poliedros com esferas inscritas ou circunscritas, eventualmente resolvido usando um método baseado em realizações de empacotamento circular, remonta ao trabalho inédito de René Descartes por volta 1630[51] e para Jakob Steiner em 1832;[34][52] os primeiros exemplos de poliedros que não têm realização com uma circunsfera ou insfera foram dados por Steinitz em 1928.[34][53] Referências ^ Weissstein, Eric W., "Gráfico poliédrico", MathWorld ^ Stormrock, Bernd (1987), "Complexos de fronteira de politopos convexos não podem ser caracterizados localmente", Jornal da Sociedade Matemática de Londres, Segunda Série, 35 (2): 314-326, CiteSeerX 10.1.1.106.3222, doi:10.1112/jlms/s2-35.2.314, MR 0881520 ^ Saltar para: a b Malkevitch, Joseph, "Técnicas para provar teoremas combinatórios sobre 3-politopos", Estruturas geométricas (notas do curso), Universidade da Cidade de Nova York ^ Ir para: a b c d Eades, Peter; Garvan, Patrick (1995), "Desenhando gráficos planares estressados ​​em três dimensões", em Brandemburgo, Francisco José (ed.), Desenho do gráfico, Simpósio sobre Desenho Gráfico, GD '95, Passau, Alemanha, Setembro 20-22, 1995, Processos, Notas de aula em Ciência da Computação, volume. 1027, Springer, pp. 212–223, doi:10.1007/BFb0021805, MR 1400675 ^ Saltar para: a b c Grünbaum, Branko (2003), "13.1 Teorema de Steinitz", Politopos Convexos, Textos de Graduação em Matemática, volume. 221 (2ª edição), Springer-Verlag, pp. 235-244, ISBN 0-387-40409-0 ^ Saltar para: a b Steinitz, Ernest (1922), "IIIAB12: poliedros e divisões do espaço", Enciclopédia de Ciências Matemáticas (em alemão), volume. Band 3 (Geometrias), pp. 1-139, Concluído em 31. Agosto 1916 ^ Mais tecnicamente, este gráfico é o 1-esqueleto; veja Grünbaum (2003), p. 138, e Ziegler (1995), p. 64. ^ Saltar para: a b Ziegler, Gunter M. (1995), "Capítulo 4: Teorema de Steinitz para 3-Polítopos", Palestras sobre Politopos, Textos de Graduação em Matemática, volume. 152, Springer-Verlag, pp. 103-126, ISBN 0-387-94365-X ^ Balinski, M. eu. (1961), "Sobre a estrutura gráfica de poliedros convexos em n-espaço", Jornal do Pacífico de Matemática, 11 (2): 431-434, doi:10.2140/pjm.1961.11.431, MR 0126765 ^ Epifanov, G. V. (1966), "Redução de um gráfico plano a uma aresta por transformações estrela-triângulo", Doklady Akademii Nauk SSSR (em russo), 166: 19-22, MR 0201337, Zbl 0149.21301 ^ Saltar para: a b Truemper, K. (1989), "Sobre a redução delta-estrela para gráficos planares", Revista de Teoria dos Grafos, 13 (2): 141-148, doi:10.1002/jgt.3190130202, MR 0994737 ^ Chang, Hsien Chih; Cossarini, Marcos; Erickson, Jeff (2019), "Limites inferiores para redução elétrica em superfícies", em Bareket, Gill; Wang, Jesus (ed.), 35º Simpósio Internacional de Geometria Computacional (SoCG 2019), Leibniz International Proceedings in Informatics (LIPics), volume. 129, Cadeira de dia, Alemanha: Schloss Dagstuhl Leibniz Centro de Ciência da Computação, pp. 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 o teorema de Steinitz sobre 3-politopos convexos e sobre algumas propriedades de grafos planares", em Chartrand, G.; Kapoor, S. F. (ed.), As muitas facetas da teoria dos grafos: Anais da Conferência realizada na Western Michigan University, Kalamazoo, MI., Outubro 31 – novembro 2, 1968, Notas de aula em matemática, volume. 110, Springer, pp. 27-40, doi:10.1007/BFb0060102, MR 0250916 ^ Maxwell, J. Atendente (1864), "Em figuras recíprocas e diagramas de forças", Revista Filosófica, 4ª Série, 27 (182): 250-261, doi:10.1080/14786446408643663 ^ Whiteley, Walter (1982), "Movimentos e tensões de poliedros projetados", Topologia Estrutural, 7: 13-38, HDL:2099/989, MR 0721947 ^ Tutte, C. T. (1963), "Como desenhar um gráfico", Anais da Sociedade Matemática de Londres, 13: 743–767, doi:10.1112/plms/s3-13.1.743, MR 0158387 ^ Brandes, Ulrik (2001), "Baseando-se em analogias físicas", em comerciante, Michael; Wagner, Dorotéia (ed.), Gráficos de desenho: Métodos e Modelos, Notas de aula em Ciência da Computação, volume. 2025, Berlim: Springer, pp. 71-86, CiteSeerX 10.1.1.9.5023, doi:10.1007/3-540-44969-8_4, MR 1880146 ^ Saltar para: a b Onn, Shmuel; rocha de tempestade, Bernd (1994), "Um teorema quantitativo de Steinitz", Contribuições para a álgebra e geometria, 35 (1): 125-129, MR 1287206 ^ Saltar para: a b c fita tingida, Ares; Rote, Gunter; Schulz, André (2011), "Embeddings de grade pequena de 3 politopos", Discrete & Computational Geometry, 45 (1): 65-87, arXiv:0908.0488, doi:10.1007/s00454-010-9301-0, MR 2765520, S2CID 10141034 ^ Brightwell, Graham R.; Scheinerman, Eduardo R. (1993), "Representações de gráficos planares", Revista SIAM sobre Matemática Discreta, 6 (2): 214-229, doi:10.1137/0406017, MR 1215229 ^ Saltar para: a b Ziegler, Gunter M. (2007), "politopos convexos: construções extremas e formas de vetor f. Seção 1.3: Teorema de Steinitz via embalagens circulares", em Miller, Esdras; Reiner, Vencedor; rocha de tempestade, Bernd (ed.), Combinatória geométrica, Série de Matemática IAS/Park City, volume. 13, Sociedade Americana de Matemática, pp. 628–642, ISBN 978-0-8218-3736-8 ^ Saltar para: a b Grünbaum (2003), teorema 13.2.3, p. 244, afirma isso em uma forma equivalente onde as coordenadas são números racionais. ^ Buchin, Kevin; Schulz, André (2010), "Sobre o número de árvores geradoras um grafo planar pode ter", na montanha, Marca; Meyer, Ulrich (ed.), Algoritmos - ESA 2010, 18º Simpósio Europeu Anual, Liverpool, Reino Unido, Setembro 6-8, 2010, Processos, Parte I, Notas de aula em Ciência da Computação, volume. 6346, Springer, pp. 110–121, CiteSeerX 10.1.1.746.942, doi:10.1007/978-3-642-15775-2_10, ISBN 978-3-642-15774-5, MR 2762847, S2CID 42211547 ^ Chrobak, Marek; Goodrich, Miguel T.; Tamássia, Roberto (1996), "Desenhos convexos de gráficos em duas e três dimensões", Anais do 12º Simpósio ACM de Geometria Computacional (SoCG '96), ACM, pp. 319–328, doi:10.1145/237218.237401, S2CID 1015103 ^ Schulz, André (2011), "Desenho de 3 politopos com boa resolução de vértices", Journal of Graph Algorithms and Applications, 15 (1): 33-52, doi:10.7155/verdade.00216, MR 2776000 ^ Demaine, Eric D.; Schulz, André (2017), "Incorporando politopos empilhados em uma grade de tamanho polinomial", Discrete & Computational Geometry, 57 (4): 782–809, arXiv:1403.7980, doi:10.1007/s00454-017-9887-6, MR 3639604, S2CID 104867 ^ Grünbaum (2003), p. 96uma. ^ Aichholzer, Oswin; Cheng, Howard; Devadoss, Satyan L.; cortar, Thomas; Huber, Stefan; Li, Brian; Risteski, Andrej (2012), "O que faz de uma árvore um esqueleto reto?" (PDF), Anais da 24ª Conferência Canadense de Geometria Computacional (CCCG'12) ^ Barnette, David W.; Grünbaum, Branko (1970), "Pré-atribuindo a forma de um rosto", Jornal do Pacífico de Matemática, 32 (2): 299-306, doi:10.2140/pjm.1970.32.299, MR 0259744 ^ Barnette, David W. (1970), "Projeções de 3 politopos", Jornal de Matemática de Israel, 8 (3): 304-308, doi:10.1007/BF02771563, MR 0262923, S2CID 120791830 ^ Hart, George W. (1997), "Calculando poliedros canônicos", Mathematica em Educação e Pesquisa, 6 (3): 5–10 ^ Berna, Marshall W.; Eppstein, Davi (2001), "Transformações ideais de Möbius para visualização de informações e geração de malha", em estiramento, Frank K. H. UMA.; Saco, Jörg-Rüdiger; Tamássia, Roberto (ed.), Algoritmos e Estruturas de Dados, 7º Workshop Internacional, WADS 2001, Providência, RI, EUA, Agosto 8-10, 2001, Processos, Notas de aula em Ciência da Computação, volume. 2125, Springer, pp. 14-25, arXiv:cs/0101006, doi:10.1007/3-540-44634-6_3, S2CID 3266233 ^ Schramm, Oded (1992), "Como engaiolar um ovo", Descobertas matemáticas, 107 (3): 543-560, Bibcode:1992InMat.107..543S, doi:10.1007/BF01231901, MR 1150601, S2CID 189830473 ^ Saltar para: a b c Rivin, Igor (1996), "Uma caracterização de poliedros ideais em 3 espaços hiperbólicos", Anais da Matemática, Segunda Série, 143 (1): 51-70, doi:10.2307/2118652, JSTOR 2118652, MR 1370757 ^ Dillencourt, Miguel B.; Smith, Warren D. (1996), "Condições grafo-teóricas para inscritibilidade e realizabilidade de Delaunay", Matemática Discreta, 161 (1-3): 63-77, doi:10.1016/0012-365X(95)00276-3, MR 1420521 ^ Saltar para: a b Eppstein, Davi; Mumford, Elena (2014), "Teoremas de Steinitz para poliedros ortogonais simples", Jornal de Geometria Computacional, 5 (1): 179-244, doi:10.20382/jocg.v5i1a10, MR 3259910, S2CID 8531578 ^ Richter-Gebert, Jürgen (1996), Espaços de Realização de Politopos, Notas de aula em matemática, volume. 1643, Springer-Verlag, CiteSeerX 10.1.1.2.3495, doi:10.1007/BFb0093761, ISBN 978-3-540-62084-6, MR 1482230 ^ Schaefer, Marco (2013), "Realização de gráficos e ligações", em Pach, John (ed.), Trinta ensaios sobre teoria dos grafos geométricos, Nova york: Springer, pp. 461–482, CiteSeerX 10.1.1.220.9651, doi:10.1007/978-1-4614-0110-0_24, MR 3205168 ^ Saltar para: a b Eppstein, Davi (2020), "As copas das árvores e seus gráficos", Discrete & Computational Geometry, 64 (2): 259-289, arXiv:1510.03152, doi:10.1007/s00454-020-00177-0, MR 4131546, S2CID 213885326 ^ Hong, Seok-Hee; Nagamochi, Hiroshi (2011), "Estendendo o teorema de Steinitz para poliedros em forma de estrela ascendente e poliedros esféricos", Algoritmica, 61 (4): 1022–1076, doi:10.1007/s00453-011-9570-x, MR 2852056, S2CID 12622357 ^ Blind, Roswitha; Mani-Levitska, Peter (1987), "Quebra-cabeças e isomorfismos politopos", Equações matemáticas, 34 (2-3): 287-297, doi:10.1007/BF01830678, MR 0921106, S2CID 120222616 ^ Kalai, Gil (1988), "Uma maneira simples de distinguir um politopo simples de seu gráfico", Jornal de Teoria Combinatória, Série A, 49 (2): 381-383, doi:10.1016/0097-3165(88)90064-7, MR 0964396 ^ Ziegler, Gunter M. (2008), "Superfícies poliédricas de alto gênero", Geometria Diferencial Discreta, Seminários de Oberwolfach, volume. 38, Springer, pp. 191–213, arXiv:matemática/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), "representações de Steinitz de poliedros e o número de Colin de Verdière", Jornal de Teoria Combinatória, Série B, 82 (2): 223-236, doi:10.1006/jctb.2000.2027, MR 1842113 ^ Saltar para: a b c Grünbaum, Branko (2007), "Gráficos de poliedros; poliedros como gráficos", Matemática Discreta, 307 (3-5): 445-463, doi:10.1016/j.disc.2005.09.037, HDL:1773/2276, MR 2287486 ^ Erickson, Jeff; Lin, Patrick (2020), "Uma correspondência toroidal Maxwell-Cremona-Delaunay", em Cabello, Sérgio; Chen, Danny Z. (ed.), 36º Simpósio Internacional de Geometria Computacional (SoCG 2020), Leibniz International Proceedings in Informatics (LIPics), volume. 164, Cadeira de dia, Alemanha: Schloss Dagstuhl Leibniz Centro de Ciência da Computação, pp. 40:1-40:17, arXiv:2003.10057, doi:10.4230/LIPics.SoCG.2020.40, ISBN 978-3-95977-143-6, S2CID 209514295 ^ Koebe, Paulo (1936), "Problemas de contato de mapeamento conforme", Relatórios sobre as negociações da Academia de Ciências da Saxônia em Leipzig: aula físico-matemática (em alemão), 88: 141–164 ^ Saltar para: a b c Stephenson, Kenneth (2003), "Embalagem circular: um conto matemático" (PDF), Avisos da American Mathematical Society, 50 (11): 1376-1388, CiteSeerX 10.1.1.101.5592, MR 2011604 ^ Saltar para: a b Andreev, E. M. (1970), "Poliedros convexos em espaços Lobačevskiĭ", Mathematicheskii Sbornik, 81 (123): 445-478, MR 0259734 ^ Schramm, Oded (1991), "Existência e singularidade de embalagens com combinatória especificada", Jornal de Matemática de Israel, 73 (3): 321-341, doi:10.1007/BF02773845, MR 1135221, S2CID 121855202; ver discussão após Corolário 3.8, p. 329 ^ Frederico, Pasquale Joseph (1982), Descartes sobre Poliedros: Um Estudo do "Dos elementos sólidos", Fontes na História da Matemática e Ciências Físicas, volume. 4, Springer, p. 52 ^ Steiner, Jacob (1832), "Pergunta 77", Desenvolvimento sistemático da dependência de formas geométricas entre si (em alemão), Berlim: G. Fincke, p. 316 ^ Steinitz, Ernest (1928), "Sobre problemas isoperimétricos com poliedros convexos", Revista de Matemática Pura e Aplicada (em alemão), 1928 (159): 133-143, doi:10.1515/crll.1928.159.133, MR 1581158, S2CID 199546274 Categorias: Gráficos planaresTeoria dos grafos geométricosCombinatória poliédricaTeoremas em teoria dos grafosTeoremas em geometria discreta