Existe um belo teorema de Koebe (veja aqui ) que afirma que qualquer gráfico planar pode ser desenhado como gráfico de beijo de discos (muito romântico ...). (Dito de maneira um pouco diferente, qualquer gráfico plano pode ser desenhado como o gráfico de interseção dos discos.)
O teorema de Koebe não é muito fácil de provar. Minha pergunta: existe uma versão mais fácil desse teorema em que, em vez de discos, é permitido o uso de formas convexas de gordura (a convexidade pode estar aberta a negociações, mas não a gordura). Observe que todo vértice pode ter uma forma diferente.
Obrigado...
Esclarecimento: Para uma forma , deixar R ( X ) ser o raio da bola envolvente menor de X , e deixá- r ( X ) me deixar o raio do maior esferas encerrado em S . A forma S é α- gorda se R ( x ) / r ( x ) ≤ α . (Esta não é a única definição de gordura, a propósito.)
fonte
Respostas:
Você não disse que os objetos gordos tinham que ser bidimensionais, não é? Felsner e Francis provam que sempre é possível com cubos paralelos aos eixos em 3d . Mas, a prova envolve as generalizações de Schramm de Koebe-Thurston-Andreev, portanto não é exatamente um resultado mais simples. Eles também mencionam ao longo do caminho que, para gráficos planares máximos de quatro conexões, é possível usar triângulos equilaterais do lado paralelo.
fonte
Se você usar triângulos, isso pode ser feito. Talvez não seja mais fácil do que Koebe ...
de Fraisseix, Ossona de Mendez e Rosenstiehl. Em gráficos de contato de triângulo. CPC 3 (2): 233-246, 1994.
fonte
Schramm provou que todo gráfico planar é o gráfico de contato de algum conjunto de objetos convexos lisos no plano em sua tese de doutorado (Princeton, 1990), usando o Teorema de Ponto Fixo de Brouwer.
Uma boa pesquisa deste e de outros resultados relacionados ao Teorema de Koebe está em uma pesquisa de Sachs .
fonte
Uma coisa que sabemos é que você não pode recriar o teorema de Koebe com retângulos. Os gráficos de contato dos retângulos não podem capturar .K4
fonte
Há um novo artigo sobre o arxiv de Duncan, Gansner, Hu, Kaufman e Kobourov sobre representações gráficas de contato. Eles mostram que polígonos de 6 lados são necessários e suficientes. Os hexágonos podem ser convexos, mas na primeira leitura não ficou claro se eles também eram gordos.
fonte
Gerd Wegner em sua tese de doutorado (Georg-August-Universität, Göttingen, 1967) provou que qualquer gráfico é o gráfico de contato de um conjunto de pólipos tridimensionais convexos (mas ele credita a Grünbaum a primeira prova não publicada do resultado). Esta é uma prova curta.
fonte