Dibujar gráficos del número de cruce acotado

El teorema de Fáry dice que se puede dibujar un gráfico plano simple sin cruces para que cada borde sea un segmento de línea recta.

Mi pregunta es si existe un teorema análogo para las gráficas del número de cruce acotado . Específicamente, ¿podemos decir que se puede dibujar un gráfico simple con el número de cruce k para que haya k cruces en el dibujo y para que cada borde sea una curva de grado como máximo f (k) para alguna función f?

EDITAR: Como observa David Eppstein, se ve fácilmente que el teorema de Fáry implica un dibujo de un gráfico con el número de cruce k, de modo que cada borde es una cadena poligonal con, como máximo, k curvas. Todavía tengo curiosidad si cada borde se puede dibujar con curvas de grado acotadas. Hsien-Chih Chang señala que f (k) = 1 si k es 0, 1, 2, 3 y f (k)> 1 de lo contrario.

Si un gráfico tiene un número de cruce limitado, se puede dibujar con ese número de cruces en el modelo de polilínea (es decir, cada borde es una cadena poligonal, mucho más común en la literatura de dibujo de gráficos que las curvas algebraicas de grado limitado) con un número limitado de curvas por borde. También es cierto de manera más general si hay un número limitado de cruces por borde. Para ver esto, simplemente planarice el gráfico (reemplace cada cruce por un vértice) y luego aplique Fáry.

Ahora, para usar esto para responder a su pregunta real, lo que debe hacer es encontrar una curva algebraica que esté arbitrariamente cerca de una polilínea dada, con un grado limitado por una función del número de curvas de polilínea. Esto también se puede hacer, con bastante facilidad. Por ejemplo: para cada segmento de la polilínea, sea e i una elipse con alta excentricidad que esté muy cerca de s i , y sea p i un polinomio cuadrático que sea positivo fuera de e i y negativo dentro de e i . Deje que su polinomio general tome la forma p = ϵ - ∏ i $s_i$$e_i$$s_i$$p_i$$e_i$$e_i$ donde ϵ es un pequeño número real positivo. Entonces, un componente de la curva p = 0 estará un poco fuera de la unión de las elipses y puede usarse para sustituir la polilínea; su grado será el doble del número de elipses, que es lineal en el número de cruces por borde.$p=\epsilon-\prod_i p_i$$\epsilon$$p=0$

Esto se conoce como la rectilíneo número cruce , que es el número mínimo de cruces entre todos los posibles dibujos en línea recta de la gráfica G . Compare con el número de cruce normal c r ( G ) , se puede ver que ¯ c r ( G ) ≥ c r ( G ) . Y su pregunta es esencialmente lo mismo que preguntar si ¯ c r ( G ) = c r ( G $\overline{\mathsf{cr}}(G)$$G$$\mathsf{cr}(G)$$\overline{\mathsf{cr}}(G) \geq \mathsf{cr}(G)$$\overline{\mathsf{cr}}(G) = \mathsf{cr}(G)$si para alguna constante k .$\mathsf{cr}(G) \leq k$$k$

En el documento Bounds para números de cruce rectilíneos , Bienstock y Dean demostraron que

Teorema. Si , tenemos ¯ c r ( G ) = c r ( G ) . Y para k ≥ 4 , hay gráficos G n con c r ( G ) = 4 y ¯ c r ( G ) ≥ n .$k \leq 3$$\overline{\mathsf{cr}}(G) = \mathsf{cr}(G)$$k \geq 4$$G_n$$\mathsf{cr}(G) = 4$$\overline{\mathsf{cr}}(G) \geq n$

Consulte una encuesta sobre los números de cruce de Richter y Salazar como referencia. Entonces, si hay una variante del teorema de Fáry en los gráficos con números de cruce acotados, se debe restringir con .$\mathsf{cr}(G) \leq 3$

Para un pequeño ejemplo con , considere la gráfica completa en 8 vértices. Tiene c r ( K 8 ) = 18 y ¯ c r ( K 8 ) = 19 .$\overline{\mathsf{cr}}(G) \neq \mathsf{cr}(G)$$\mathsf{cr}(K_8) = 18$$\overline{\mathsf{cr}}(K_8) = 19$