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?
@ 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
fuente