Grafik planar melalui persimpangan benda gemuk?

14

Ada teorema Koebe yang indah (lihat di sini ) yang menyatakan bahwa grafik planar apa pun dapat digambar sebagai grafik ciuman disk (sangat romantis ...). (Dengan kata lain, grafik planar dapat digambarkan sebagai grafik persimpangan disk.)

Teorema Koebe tidak mudah dibuktikan. Pertanyaan saya: Apakah ada versi yang lebih mudah dari teorema ini di mana alih-alih cakram, orang dapat menggunakan bentuk lemak cembung apa pun (cembung mungkin terbuka untuk negosiasi, tetapi bukan kegemukan). Perhatikan, bahwa setiap simpul bisa berbentuk berbeda.

Terima kasih...

Klarifikasi: Untuk bentuk , biarkan R ( X ) menjadi jari-jari melampirkan bola terkecil dari X , dan membiarkan r ( X ) biar jari-jari bola tertutup terbesar di S . Bentuk S adalah α- lemak jika R ( x ) / r ( x ) α . (Ini bukan satu-satunya definisi untuk kegemukan, BTW.)XR(X)Xr(X)SSαR(x)/r(x)α

Sariel Har-Peled
sumber
menjadi sedikit bertele-tele: teorema Koebe adalah tentang grafik kontak, yang sedikit berbeda dengan grafik persimpangan. Versi mana yang Anda inginkan?
Suresh Venkat
Jadi saya berasumsi kegemukan diperlukan karena fakta bahwa setiap grafik planar adalah grafik persimpangan segmen dalam pesawat (Chalopin & Gonçalves, STOC 09). Jika mereka tidak gemuk, maka ciuman sama dengan persimpangan. (Hm, kalimat terakhir aneh di luar konteks!)
RJK
Kegemukan hanya membuat hidup lebih mudah sejauh melakukan hal-hal lain dengan grafik (misalnya, menemukan pemisah).
Sariel Har-Peled
3
Saya bertanya-tanya apakah pertanyaan sebenarnya di sini adalah: "berikan bukti sederhana teorema Koebe" daripada "temukan keluarga bentuk lemak kompleksitas rendah yang mensimulasikan teorema Koebe"
Suresh Venkat
2
Tentu. Itu interpretasi yang valid. Namun, saya pikir untuk mendapatkan bukti sederhana dari teorema Koebe, kita perlu membuatnya santai ...
Sariel Har-Peled

Jawaban:

10

Anda tidak mengatakan benda gemuk itu harus dua dimensi, bukan? Felsner dan Francis membuktikan bahwa itu selalu mungkin dengan kubus sumbu-paralel dalam 3d . Tapi, buktinya melibatkan generalisasi Schramm tentang Koebe-Thurston-Andreev, jadi itu bukan hasil yang lebih sederhana. Mereka juga menyebutkan sepanjang jalan bahwa untuk graf planar maksimal empat terhubung, dimungkinkan untuk menggunakan segitiga sama sisi paralel.

David Eppstein
sumber
Yah, itu pertanyaan yang bagus juga, saya kira. Apakah ada bukti cepat bahwa setiap grafik planar direpresentasikan sebagai grafik kontak bola?
RJK
7

Schramm membuktikan bahwa setiap grafik planar adalah grafik kontak dari beberapa set objek cembung halus di pesawat dalam tesis PhD-nya (Princeton, 1990) menggunakan Brouwer's Fixed Point Theorem.

Sebuah survei yang bagus tentang ini dan hasil lainnya yang terkait dengan Teorema Koebe ada dalam survei oleh Sachs .

RJK
sumber
6

Satu hal yang kami tahu adalah bahwa Anda tidak dapat membuat kembali teorema Koebe dengan persegi panjang. Grafik kontak persegi panjang tidak dapat menangkap .K4

Suresh Venkat
sumber
Sumbu persegi panjang paralel? Atau persegi panjang?
Sariel Har-Peled
sumbu paralel persegi panjang.
Suresh Venkat
4

Ada kertas baru di arxiv oleh Duncan, Gansner, Hu, Kaufman dan Kobourov tentang representasi grafik kontak. Mereka menunjukkan bahwa 6 poligon sisi diperlukan dan cukup. Segi enam bisa cembung, tetapi tidak jelas bagi saya pada bacaan pertama apakah mereka juga gemuk.

Suresh Venkat
sumber
Yo yo. Saya baru saja menemukan makalah ini sendiri ... Mereka menggunakan hasil et de de Fraisseix yang disebutkan di atas, dan hasil oleh Kant ...
Sariel Har-Peled
Di sini "kontak" didefinisikan secara berbeda. Kontak titik tidak diizinkan, dari bacaan saya.
RJK
Saya membayangkan itu masuk akal untuk representasi poligon (karena kontak non-verteks tentu akan menjadi non-point)?
Suresh Venkat
Karena di sini hanya ada tiga slop yang diizinkan, sentuhan harus melalui tepi paralel yang saling menyentuh ... Tidak?
Sariel Har-Peled
0

Gerd Wegner di nya tesis PhD (Georg-August-Universität, Göttingen, 1967) membuktikan bahwa grafik apapun adalah grafik kontak dari satu set polytopes cembung tiga-dimensi (tapi dia kredit bukti yang tidak dipublikasikan pertama hasil untuk Grünbaum). Ini bukti singkat.

RJK
sumber
Ada bukti langsung yang mudah tentang itu, misalnya dengan meletakkan titik pada kurva momen dan menghitung diagram Voronoi mereka. Namun, kondisi kegemukan ini gagal total ...
Sariel Har-Peled
Ah, saya benar-benar salah paham "gemuk". Saya malu untuk mengakui (tapi saya kira itu harus jelas sekarang) bahwa saya tidak tahu definisi, sampai saya googled "segitiga lemak". Bisakah Anda memberikan referensi / definisi untuk konsep ini?
RJK
Juga, representasi yang saya sebutkan dapat digunakan untuk mewakili grafik apa pun dengan cara ini - tidak hanya grafik planar.
Sariel Har-Peled
Terima kasih atas klarifikasi "gemuk" dalam pertanyaan. Pantas menunjukkan bahwa saya tidak menyebutkan planar baik dalam posting ini. Untuk nilai kegemukan yang diberikan, masing-masing grafik diwakili oleh polytopes lemak cembung dalam beberapa (cukup tinggi) dimensi. Pertanyaan yang jelas adalah apakah dimensi terikat dapat seragam pada semua grafik. Apakah ini sudah dipelajari?
RJK
Tidak sejauh yang saya tahu, tapi saya tidak terlalu tahu tentang hal-hal seperti itu ...
Sariel Har-Peled