Representar gráficos no planos con círculos superpuestos

16

Sabemos que podemos representar cualquier gráfico plano mediante un conjunto de círculos en el plano, conocido como gráfico de monedas . Cada círculo representa un vértice y hay un borde entre dos vértices si y solo si los círculos se "besan" en su límite.

¿Supongamos que permitimos que los círculos se superpongan y representen un borde por un par de círculos que se cruzan en su interior? ¿Qué clase de gráficos podemos representar en este modelo? Claramente podemos representar gráficos completos (cada círculo se cruza con cualquier otro círculo). ¿Podemos representar todos los gráficos como este?

Joe
fuente

Respuestas:

19

El artículo definitivo es un artículo de Hlineny y Kratochvil de 2001. En él muestran que el problema de reconocer un gráfico de intersección de disco (su pregunta) es NP-hard, lo que sugiere que será difícil llegar a una caracterización limpia. También señalan que no se pueden representar como la intersección de los discos, respondiendo la otra parte de su pregunta.K3,3

Suresh Venkat
fuente
77
Más precisamente, debería ser cierto que el problema está completo para la teoría de la decisión existencial de los reales. Esto se conoce para los gráficos de intersección de unidades de disco; consulte homepages.cwi.nl/~mueller/Papers/SphericityDotproduct.pdf , pero no conozco una referencia para los gráficos de intersección de discos arbitrarios.
David Eppstein
77
Además, uno puede mostrar usando argumentos de dimensión VC que la familia de cualquier gráfico de intersección definido por formas "simples" es bastante limitado y no puede incluir muchos gráficos. En particular, hay un gráfico de tamaño constante que no pueden inducir.
Sariel Har-Peled
9

nortenorte3norteΘ(1)norte2(norte2)nortenortenorteΘ(1)nortenorte
Θ(1)norteCnorteCnorteC,C>0 0

@ David: ¡Gracias por mencionar mi trabajo!
Tampoco conozco ningún documento que haga la reducción a la teoría existencial de los reales (ERT) para gráficos de disco arbitrarios. Sin embargo, en otro documento con McDiarmid , dimos una construcción para "incrustar" arreglos de línea en un gráfico de disco que podría convertirse en una prueba de integridad para ERT con algún trabajo adicional en la línea de lo que hicimos en el papel con Kang.

Tobias Mueller

Tobias Mueller
fuente