Gráfico más simple que no es un gráfico de la intersección de segmentos

Question

Dado un conjunto finito $S=\{s_1,s_2,\ldots,s_n\}$ en línea recta de los segmentos en el plano, sus intersección de la gráfica de $G(S)$ es un gráfico que contiene un vértice $v_i$ para cada segmento de $s_i\in S$, y un borde de $v_iv_j$ para cada par de segmentos de $s_i, s_j$ que se intersectan.

Vamos a llamar a un gráfico de $G$ una intersección de la gráfica , si existe una colección de línea recta en segmentos de $S$ tal que $G(S)=G$.

Que es el más simple (o relativamente simple) gráfico de $G$ que es no una intersección de la gráfica?

(De fondo: No todos los gráficos son de intersección de los gráficos, ya que el número de $n$-vértice de intersección de las gráficas es sólo $2^{O(n\log n)}$ (no se puede encontrar la referencia ahora mismo), mientras que el número total de $n$-vértice gráficos es $2^{\Theta(n^2)}$.)

Answer 1

Todo lo que usted necesita es un gráfico que consta de vértices y aristas que representan los segmentos que son imposibles en su geometría.

Considere la posibilidad de una intersección de la gráfica con un conjunto de vértices que contiene ocho elementos $v_1$ a través de $v_8$. Deje que los bordes se define de forma tal que $v_1$ intersecta $v_2$ y $v_8$, $v_2$ cruza $v_1$$v_3$, ... etc. Cualquier modelo geométrico de este gráfico, que debe producir un cerrado de ocho lados del polígono.

Para cada arista $e_{xy}$ en el gráfico, añadir cinco nuevos vértices $w_{xyab}$ donde $a$ $b$ son los pares de segmentos en el octágono que se cruzan, y $a \ne b \ne x \ne y$. Cada una de las $w_{xyab}$ cruza $v_a$, $v_b$, $v_x$, y $v_y$, pero nunca las $w$.

Creo que este es un gráfico en el que es imposible para el modelo de intersección de segmentos coplanarios. Prueba a seguir.

Answer 2

Creo que tengo la solución: Tomar un no plana gráfico, decir $K_5$. Agregar un vértice en el centro de cada borde. Podemos obtener un gráfico de $G$ $5$ "azul" vértices de grado $4$ $5$ "rojo" vértices de grado $2$. Creo $G$ no es realizable como una intersección de la gráfica de los segmentos. Si lo fuera, podríamos obtener un plano de la incorporación de la $K_5$ por poner un vértice arbitrariamente en cada uno azul segmento, y unir los vértices de uno al otro con el modelo lineal por tramos de arcos que van muy cerca de la blue segmentos, y a través de la red segmentos.