Merupakan grafik non-planar dengan lingkaran yang tumpang tindih

16

Kita tahu bahwa kita dapat mewakili grafik planar apa pun dengan seperangkat lingkaran di pesawat, yang dikenal sebagai grafik koin . Setiap lingkaran mewakili sebuah simpul dan ada sebuah tepi di antara dua simpul jika dan hanya jika lingkaran "mencium" pada batasnya.

Misalkan sebaliknya kita membiarkan lingkaran untuk tumpang tindih, dan mewakili tepi oleh sepasang lingkaran yang berpotongan di interior mereka? Kelas grafik apa yang dapat kami wakili dalam model ini? Jelas kami dapat mewakili grafik lengkap (setiap lingkaran memotong setiap lingkaran lainnya). Bisakah kita mewakili semua grafik seperti ini?

Joe
sumber

Jawaban:

19

Artikel definitif adalah makalah oleh Hlineny dan Kratochvil dari 2001. Di dalamnya mereka menunjukkan bahwa masalah mengenali grafik persimpangan disk (pertanyaan Anda) adalah NP-hard, yang menunjukkan bahwa akan sulit untuk menghasilkan karakterisasi yang bersih. Mereka juga menunjukkan bahwa tidak dapat direpresentasikan sebagai persimpangan disk, menjawab bagian lain dari pertanyaan Anda.K3,3

Suresh Venkat
sumber
7
Lebih tepatnya memang benar bahwa masalahnya lengkap untuk teori keputusan eksistensial real. Ini dikenal untuk grafik persimpangan disk unit - lihat homepages.cwi.nl/~mueller/Papers/SphericityDotproduct.pdf - tapi saya tidak tahu referensi untuk grafik persimpangan disk sewenang-wenang.
David Eppstein
7
Juga, seseorang dapat menunjukkan menggunakan argumen dimensi VC bahwa keluarga dari setiap grafik persimpangan didefinisikan oleh bentuk "sederhana" sangat terbatas dan tidak dapat memasukkan banyak grafik. Secara khusus, ada grafik ukuran konstan yang tidak dapat mereka hasilkan.
Sariel Har-Peled
9

Dalam sebuah makalah dengan McDiarmid kami menunjukkan bahwa jumlah grafik berlabel pada simpul yang merupakan grafik persimpangan disk adalah n 3 nΘ ( 1 ) n yang jauh lebih kecil dari 2 ( nnn3nΘ(1)n , jumlah total grafik berlabel padansimpul, dan lebih banyak dari itunnΘ(1)n, jumlah grafik planar (menyentuh grafik disk) padansimpul. (Di sini saya maksud denganΘ(1)njumlah yang dibatasi di bawah ini olehcndan di atas olehCnuntuk beberapa konstanta c,C>0.) 2(n2)nnnΘ(1)nn
Θ(1)ncnCnc,C>0

@ David: Terima kasih telah menyebutkan pekerjaan saya!
Saya juga tidak mengetahui ada kertas yang melakukan reduksi ke teori eksistensial real (ERT) untuk grafik disk sewenang-wenang. Namun, dalam makalah lain dengan McDiarmid , kami memberikan konstruksi untuk "menyematkan" pengaturan garis dalam grafik disk yang dapat diubah menjadi bukti kelengkapan untuk ERT dengan beberapa pekerjaan tambahan sesuai dengan apa yang kami lakukan di kertas dengan Kang.

Tobias Mueller

Tobias Mueller
sumber