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.)
sumber
Jawaban:
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.
sumber
Jika Anda menggunakan segitiga, itu bisa dilakukan. Mungkin tidak lebih mudah daripada Koebe ...
de Fraisseix, Ossona de Mendez dan Rosenstiehl. Pada Grafik Kontak Segitiga. BPK 3 (2): 233-246, 1994.
sumber
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 .
sumber
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
sumber
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.
sumber
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.
sumber