Hay un hermoso teorema de Koebe (ver aquí ) que establece que cualquier gráfico plano se puede dibujar como un gráfico de besos de discos (muy romántico ...). (Dicho de otra manera, cualquier gráfico plano se puede dibujar como el gráfico de intersección de los discos).
El teorema de Koebe no es muy fácil de probar. Mi pregunta: ¿Existe una versión más fácil de este teorema en la que en lugar de discos se permita usar formas convexas gruesas (la convexidad podría estar abierta a negociaciones, pero no a la gordura). Tenga en cuenta que cada vértice puede tener una forma diferente.
Gracias...
Aclaración: Para una forma , dejar que R ( X ) es el radio de la bola envolvente más pequeña de X , y dejar que r ( X ) me dejar que el radio de la bola más grande encerrado en S . La forma S es grasa α si R ( x ) / r ( x ) ≤ α . (Esta no es la única definición de gordura, por cierto).
fuente
Respuestas:
No dijiste que los objetos gordos tenían que ser bidimensionales, ¿verdad? Felsner y Francis demuestran que siempre es posible con cubos paralelos a ejes en 3d . Pero, la prueba involucra las generalizaciones de Schramm de Koebe-Thurston-Andreev, por lo que no es exactamente un resultado más simple. También mencionan en el camino que para los gráficos planos máximos de cuatro conectados es posible utilizar triángulos equiláteros de lados paralelos.
fuente
Si usa triángulos, se puede hacer. Aunque quizás no sea más fácil que Koebe ...
de Fraisseix, Ossona de Mendez y Rosenstiehl. En los gráficos de contacto triangular. CPC 3 (2): 233-246, 1994.
fuente
Schramm demostró que cada gráfico plano es el gráfico de contacto de algún conjunto de objetos convexos lisos en el plano en su tesis doctoral (Princeton, 1990) usando el Teorema de punto fijo de Brouwer.
Una buena encuesta de este y otros resultados relacionados con el Teorema de Koebe se encuentra en una encuesta realizada por Sachs .
fuente
Una cosa que sí sabemos es que no se puede recrear el teorema de Koebe con rectángulos. Los gráficos de contacto de los rectángulos no pueden capturarK4 4
fuente
Hay un nuevo documento sobre el arxiv por Duncan, Gansner, Hu, Kaufman y Kobourov sobre representaciones de gráficos de contacto. Muestran que los polígonos de 6 lados son necesarios y suficientes. Los hexágonos pueden ser convexos, pero en una primera lectura no estaba claro si también eran gordos.
fuente
Gerd Wegner en su tesis doctoral (Georg-August-Universität, Göttingen, 1967) demostró que cualquier gráfico es el gráfico de contacto de un conjunto de politopos convexos tridimensionales (pero acredita la primera prueba no publicada del resultado a Grünbaum). Esta es una prueba corta.
fuente