¿Gráfico plano a través de la intersección de las cosas gordas?

14

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).XR(X)Xr(X)SSαR(x)/r(x)α

Sariel Har-Peled
fuente
ser un poco pedante: el teorema de Koebe se trata de gráficos de contacto, que son ligeramente diferentes a los gráficos de intersección. Qué versión prefiere ?
Suresh Venkat
Por lo tanto, supongo que se requiere gordura debido al hecho de que cada gráfico plano es el gráfico de intersección de segmentos en el plano (Chalopin & Gonçalves, STOC 09). Si no son gordos, besarse es lo mismo que intersección. (¡Hm, la última oración es extraña sacada de contexto!)
RJK
La gordura solo facilita la vida en cuanto a hacer otras cosas con el gráfico (por ejemplo, encontrar un separador).
Sariel Har-Peled
3
Me pregunto si la verdadera pregunta aquí es: "dar una prueba simple del teorema de Koebe" en lugar de "encontrar familias de formas grasas de baja complejidad que simulen el teorema de Koebe"
Suresh Venkat
2
Seguro. Esa es una interpretación válida. Sin embargo, creo que para obtener una prueba simple del teorema de Koebe, uno necesita relajarlo de alguna manera ...
Sariel Har-Peled

Respuestas:

10

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.

David Eppstein
fuente
Bueno, esa es una buena pregunta también, supongo. ¿Existe una prueba rápida de que cada gráfico plano es representable como el gráfico de contacto de esferas?
RJK
6

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

Suresh Venkat
fuente
Eje rectángulos paralelos? ¿O algún rectángulo?
Sariel Har-Peled
Eje rectángulos paralelos.
Suresh Venkat
4

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.

Suresh Venkat
fuente
Yo yo Acabo de descubrir este documento yo mismo ... Están utilizando el resultado de De Fraisseix etal mencionado anteriormente, y un resultado de Kant ...
Sariel Har-Peled
Aquí "contacto" se define de manera diferente. El punto de contacto no está permitido, de mi lectura.
RJK
Me imagino que es razonable para las representaciones poligonales (ya que cualquier contacto no vértice será necesariamente no puntual).
Suresh Venkat
Como aquí solo hay tres pendientes permitidas, el toque debe ser a través de bordes paralelos que se tocan ... ¿No?
Sariel Har-Peled
0

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.

RJK
fuente
Hay pruebas directas de eso, por ejemplo, al poner puntos en la curva de momento y calcular su diagrama de Voronoi. Aquí la condición de gordura, sin embargo, falla miserablemente ...
Sariel Har-Peled
Ah, entendí completamente mal "gordo". Me da vergüenza admitir (pero supongo que debe quedar claro ahora) que no sabía la definición, hasta que busqué en Google "triángulo gordo". ¿Podría por favor proporcionar una referencia / definición para este concepto?
RJK
Además, la representación que menciono se puede usar para representar cualquier gráfico de esta manera, no solo gráficos planos.
Sariel Har-Peled
Gracias por la aclaración de "gordo" en la pregunta. Vale la pena señalar que tampoco mencioné planar en esta publicación. Para un valor dado de gordura, cada gráfico es representable por politopos convexos de grasa en alguna dimensión (lo suficientemente alta). La pregunta obvia es si el límite en la dimensión puede ser uniforme en todos los gráficos. ¿Se ha estudiado esto?
RJK
No que yo sepa, pero no soy muy conocedor de tales cosas ...
Sariel Har-Peled