Desenhando gráficos do número da passagem delimitada

O teorema de Fáry diz que um simples gráfico plano pode ser desenhado sem cruzamentos, de modo que cada aresta seja um segmento de linha reta.

Minha pergunta é se existe um teorema análogo para gráficos de número de cruzamento delimitado . Especificamente, podemos dizer que um gráfico simples com o número de cruzamento k pode ser desenhado para que haja k cruzamentos no desenho e para que cada aresta seja uma curva de grau no máximo f (k) para alguma função f?

EDIT: Como observa David Eppstein, é fácil perceber que o teorema de Fáry implica um desenho de um gráfico com número de cruzamento k, de modo que cada aresta seja uma cadeia poligonal com no máximo k curvas. Ainda estou curioso para saber se cada aresta pode ser desenhada com curvas de graus delimitadas. Hsien-Chih Chang aponta que f (k) = 1 se k for 0, 1, 2, 3 e f (k)> 1 caso contrário.

Se um gráfico tiver um número de cruzamento delimitado, ele pode ser desenhado com esse número de cruzamentos no modelo de polilinha (ou seja, cada aresta é uma cadeia poligonal, muito mais comum na literatura de desenho de gráficos do que curvas algébricas de grau delimitado) com um número limitado de dobras por aresta. Também é verdade mais geralmente se houver um número limitado de cruzamentos por aresta. Para ver isso, basta planejar o gráfico (substitua cada cruzamento por um vértice) e aplique Fáry.

Agora, para usar isso para responder à sua pergunta real, o que você precisa fazer é encontrar uma curva algébrica arbitrariamente próxima a uma dada polilinha, com o grau limitado por uma função do número de dobras da polilinha. Isso também pode ser feito com bastante facilidade. Por exemplo: para cada segmento da polilinha, seja uma elipse com alta excentricidade muito próxima de e seja um polinômio quadrático positivo fora de e negativo dentro de . Deixe seu polinômio geral assumir a forma que é um pequeno número real positivo. Então um componente da curva$s_i$$e_i$$s_i$$p_i$$e_i$$e_i$$p=\epsilon-\prod_i p_i$$\epsilon$$p=0$ficará um pouco fora da união das elipses e pode ser usado para substituir a polilinha; seu grau será o dobro do número de elipses, que é linear no número de cruzamentos por aresta.

Isto é conhecido como o número de cruzamentos de rectilíneo , que é o número mínimo de passagens de entre todos os possíveis desenhos em linha recta do gráfico . Compare com o número de cruzamento normal , pode-se ver que . E sua pergunta é essencialmente a mesma que perguntar se se para obter alguma constante .$\overline{\mathsf{cr}}(G)$$G$$\mathsf{cr}(G)$$\overline{\mathsf{cr}}(G) \geq \mathsf{cr}(G)$$\overline{\mathsf{cr}}(G) = \mathsf{cr}(G)$$\mathsf{cr}(G) \leq k$$k$

No artigo Limites para números de cruzamento retilíneos , Bienstock e Dean provaram que

Teorema. Se , temos . E para , existem gráficos com e .$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$

Veja Uma pesquisa sobre cruzamento de números de Richter e Salazar para referência. Portanto, se existe uma variante do teorema de Fáry em gráficos com números de cruzamento limitados, ela deve ser restringida com .$\mathsf{cr}(G) \leq 3$

Para um pequeno exemplo com , considere o gráfico completo em 8 vértices. Possui e .cr(K8)=18 ¯ c r (K8)=$\overline{\mathsf{cr}}(G) \neq \mathsf{cr}(G)$$\mathsf{cr}(K_8) = 18$$\overline{\mathsf{cr}}(K_8) = 19$