Menggambar grafik dari nomor persimpangan dibatasi

Teorema Fáry mengatakan bahwa grafik planar sederhana dapat digambar tanpa penyilangan sehingga setiap sisi adalah segmen garis lurus.

Pertanyaan saya adalah apakah ada teorema analog untuk grafik bilangan persimpangan terbatas . Secara khusus, dapatkah kita mengatakan bahwa grafik sederhana dengan bilangan persimpangan k dapat digambar sehingga ada penyilangan k dalam gambar dan sehingga setiap tepi paling banyak merupakan kurva derajat paling banyak f (k) untuk beberapa fungsi f?

EDIT: Seperti yang dikatakan David Eppstein, mudah dilihat bahwa teorema Fáry menyiratkan gambar grafik dengan bilangan persimpangan k sehingga setiap sisi adalah rantai poligon dengan paling banyak k bengkok. Saya masih penasaran apakah masing-masing sisi dapat digambar dengan kurva derajat yang dibatasi. Hsien-Chih Chang menunjukkan bahwa f (k) = 1 jika k adalah 0, 1, 2, 3, dan f (k)> 1 sebaliknya.

Jika grafik telah membatasi bilangan persimpangan, dapat digambar dengan jumlah penyilangan dalam model polyline (yaitu setiap tepi adalah rantai poligon, jauh lebih umum dalam literatur gambar grafik daripada kurva aljabar tingkat-terikat) dengan jumlah bengkok yang dibatasi. per tepi. Ini juga berlaku lebih umum jika ada jumlah penyeberangan yang dibatasi per tepinya. Untuk melihat ini, cukup rencanakan grafik (ganti setiap persimpangan dengan titik) dan kemudian terapkan Fáry.

Sekarang, untuk menggunakan ini untuk menjawab pertanyaan Anda yang sebenarnya, apa yang perlu Anda lakukan adalah menemukan kurva aljabar yang secara sewenang-wenang dekat dengan polyline yang diberikan, dengan derajat yang dibatasi oleh fungsi jumlah bengkokan polyline. Ini juga bisa dilakukan, cukup mudah. Misalnya: untuk setiap segmen dari polyline, biarkan menjadi elips dengan eksentrisitas tinggi yang sangat dekat dengan , dan biarkan menjadi polinomial kuadratik yang positif di luar dan negatif di dalam . Biarkan keseluruhan polinomial Anda mengambil bentuk mana adalah bilangan real positif kecil. Kemudian satu komponen dari kurva$s_i$$e_i$$s_i$$p_i$$e_i$$e_i$$p=\epsilon-\prod_i p_i$$\epsilon$$p=0$akan terletak sedikit di luar penyatuan elips dan dapat digunakan untuk menggantikan polyline; derajatnya akan dua kali lipat jumlah elips, yang linear dalam jumlah perlintasan per sisi.

Hal ini dikenal sebagai bujursangkar jumlah persimpangan , yang merupakan jumlah minimum penyeberangan antara semua kemungkinan gambar garis lurus dari grafik G . Bandingkan dengan angka persimpangan normal c r ( G ) , orang dapat melihat bahwa ¯ c r ( G ) ≥ c r ( G ) . Dan pertanyaan Anda pada dasarnya sama dengan menanyakan apakah ¯ 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)$jika untuk beberapa konstanta k .$\mathsf{cr}(G) \leq k$$k$

Di koran Bounds untuk bilangan persimpangan bujursangkar , Bienstock dan Dean membuktikan hal itu

Dalil. Jika , kita memiliki ¯ c r ( G ) = c r ( G ) . Dan untuk k ≥ 4 , ada grafik G n dengan c r ( G ) = 4 dan ¯ 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$

Lihat survei tentang nomor persimpangan oleh Richter dan Salazar untuk referensi. Jadi jika ada varian teorema Fáry pada grafik dengan bilangan berpotongan yang dibatasi, maka harus dibatasi dengan .$\mathsf{cr}(G) \leq 3$

Untuk contoh kecil dengan , pertimbangkan grafik lengkap pada 8 simpul. Ini memiliki c r ( K 8 ) = 18 dan ¯ c $\overline{\mathsf{cr}}(G) \neq \mathsf{cr}(G)$$\mathsf{cr}(K_8) = 18$ .$\overline{\mathsf{cr}}(K_8) = 19$