Menggambar grafik dengan beberapa simpul "tajam"?

15

Untuk penyisipan planar grafik planar pada bidang dengan tepi lurus, tentukan simpul sebagai simpul tajam jika sudut maksimum antara dua tepi berturut-turut di sekitarnya adalah lebih dari 180. Atau dengan kata lain, jika ada garis yang melewatinya vertex di embedding sedemikian rupa sehingga semua tepi insiden pada vertex itu terletak di satu sisi garis, maka verteks itu "tajam" kalau tidak, itu bukan. Juga, mari kita khawatirkan hanya tentang simpul dengan derajat setidaknya 3.

Saya ingin menggambar grafik planar dengan beberapa simpul yang tajam. Adakah yang pernah mempelajari gambar seperti itu sebelumnya?

Secara khusus, saya ingin menggambar grafik planar dengan derajat maks 3 sehingga jumlah simpul tajam derajat 3 dalam embedding adalah dan koordinat simpul dapat dituliskan dengan jumlah bit polinomial.O(log⁡n)

Inilah yang dapat saya temukan setelah menghabiskan waktu di Google Cendekia:

Ukuran ketajaman verteks saya terkait dengan konsep yang sudah dipelajari yang disebut Resolusi Sudut . Dari Wikipedia:

Resolusi sudut dari suatu gambar grafik mengacu pada sudut paling tajam yang dibentuk oleh dua sisi yang bertemu pada titik sudut yang sama dari gambar tersebut.

Jadi gambar planar dengan resolusi sudut sekitar derajat 3 simpul akan baik untuk tujuan saya.π/2

Untuk simpul dengan derajat dalam gambar, resolusi sudut di sekitarnya paling banyak 2 π / dd2π/d .

Pertanyaan apakah ini ketat telah dipelajari di masa lalu, tetapi saya hanya dapat menemukan hasil asimptotik. Sebagai contoh, Malitz dan Papakostas membuktikan bahwa grafik planar dengan derajat maksimum dapat digambar dengan resolusi sudut α d . Tetapi hasil ini tidak memberikan batas yang baik untuk kasus ketika d = 3 .dαdd=3

graph-theory cg.comp-geom graph-drawing Vinayak Pathak
sumber
2
Tidak yakin apa maksudnya. Jika Anda menggambar poligon cembung biasa, sudut maks di sekitarnya lebih dari 180. Dan poligon cembung biasa dengan n besar cukup jauh dari "tajam".
Suresh Venkat
Saya mendefinisikan ketajaman sebagai properti dari vertex, bukan keseluruhan gambar. Jadi jika untuk sebuah titik, garis lurus dapat ditarik sehingga semua sisi insiden pada titik itu terletak di satu sisi garis lurus, maka titik tersebut "tajam" kalau tidak, itu bukan. Hmm, mungkin saya harus menulis ini di pertanyaan awal.
Vinayak Pathak
@ Vinayak: bagaimana dengan simpul dengan derajat 1 dan 2?
Marzio De Biasi
Mereka bisa diabaikan.
Vinayak Pathak
Jika resolusi sudut adalah yang Anda inginkan, itu masuk akal karena itu melihat sudut MINIMUM antara tepi yang berdekatan. itu sangat berbeda dengan apa yang Anda definisikan sebelumnya.
Suresh Venkat

Jawaban:

13

Dimungkinkan untuk membuat grafik planar 3-reguler Θ(n)komponen yang tidak terhubung (lihat misalnya gbr. 16 dari makalah ini ), yang masing-masing harus mengandung setidaknya satu simpul tajam.

Di sisi lain, jika Anda memerlukan tingkat konektivitas yang lebih tinggi, Anda dapat menghindari memiliki banyak simpul yang tajam. Secara khusus, jika Anda memiliki grafik planar 3-terhubung, dapat ditarik (misalnya dengan menggunakan teorema Steinitz untuk menemukan representasi polihedral dan kemudian membentuk proyeksi perspektif) sedemikian rupa sehingga semua wajah cembung, yang hanya menyebabkan wajah luar menjadi tajam. Tetapi setiap grafik planar 3-koneksi dapat disematkan sedemikian rupa sehingga permukaan luar memiliki paling banyak lima simpul (kasus terburuk adalah dodecahedron) sehingga Anda dapat menggambar setiap grafik planar 3-terhubung (3-reguler atau tidak) dengan di sebagian besar lima simpul tajam.

David Eppstein
sumber