Sifat grafik planar mana yang digeneralisasikan ke dimensi / hypergraph yang lebih tinggi?

Sebuah graf planar adalah grafik yang dapat tertanam di pesawat, tanpa harus melintasi tepi.

Misalkan menjadi k -seragam-hypergraph, yaitu hypergraph sedemikian rupa sehingga semua hyperedges-nya memiliki ukuran k.$G=(X,E)$$k$

Telah ada beberapa pekerjaan yang dilakukan untuk menanamkan hypergraph di pesawat (dengan konteks pengelompokan atau aplikasi lain), tetapi seringkali, data tidak dapat tertanam di dalam pesawat. Solusinya bisa dengan memaksanya, dengan beberapa kerugian, atau menanamkannya dalam dimensi yang lebih tinggi seperti yang saya sarankan di sini:

Sebuah perpanjangan alami dari planarity (IMO, setidaknya) adalah " -Simple-embedding" (ada nama yang berbeda dikenal untuk itu?) Dari G : sebuah embedding M : X → R k , sehingga terdapat permukaan yang menghubungkan semua simpul dari masing-masing hyperedge, dan ini tidak berpotongan kecuali untuk titik akhir.$k$$G$$\mathcal{M}:X\to \mathbb{R}^k$

(Pikirkan analog dalam 2D, di mana setiap permukaan adalah tepi yang dapat Anda gambar sesuka Anda).

Berikut ini adalah contoh 3-uniform-hypergraph 3-uniform-embedding yang valid. (Setiap simpul diwarnai oleh hyperedges yang terkandung di dalamnya, dan setiap wajah mewakili hyperedge).

Contoh lain dari grafik 3-sederhana adalah 3-uniform-hypergraph pada 5 simpul . Untuk melihat ini cukup ambil 4 poin di R 3 yang tidak terletak pada bidang 2D, buat segitiga piramida (cembung cembung mereka), dan tempatkan titik kelima di tengah piramida, sambungkan ke simpul lain.$G=(V,V\times V\times V)$$\mathbb{R}^3$

Demikian pula, tampaknya 3-uniform-hypergraph pada 6 simpul tidak memiliki embedding 3-sederhana.

Ada beberapa sifat yang sangat berguna dari grafik planar yang memungkinkan peningkatan algoritma untuk masalah-masalah sulit ketika grafik tersebut planar. Sayangnya, data seringkali tidak planar, meskipun terkadang memiliki dimensi rendah. Saya pikir memahami sifat-sifat grafik planar yang akan digeneralisasi akan membantu kita mengetahui algoritma mana yang dapat diadaptasi untuk dimensi yang lebih tinggi dengan alat yang sama.

Contoh properti yang dapat berguna berasal dari Teorema Fáry yang menyarankan setiap grafik planar dapat disematkan sedemikian rupa sehingga semua tepinya adalah segmen garis lurus.

$k$

Adakah properti lain yang bisa digeneralisasi? misalnya, dapatkah rumus Euler untuk grafik planar digeneralisasikan ke dimensi yang lebih tinggi? (walaupun saat ini saya tidak yakin apa artinya itu).

Sebagai komentar pertama, fokus Anda tampaknya pada hypergraphs tapi saya pikir sebagian besar literatur tentang menanamkan hypergraphs lebih suka bekerja dengan kompleks sederhana. Referensi yang bagus untuk pertanyaan-pertanyaan ini adalah makalah ini oleh Matousek, Tancer dan Wagner.

Apakah Teorema Fáry memiliki dimensi yang lebih tinggi?

Jawabannya adalah tidak.

Sebenarnya ada 3 konsep yang berbeda tentang embeddability: dengan lurus, piecewise-linear dan kontinu (hyper) -edges. Di pesawat, mereka semua bertepatan, tetapi secara umum tidak. Mengenai pernikahan garis lurus, contoh tandingan pertama adalah karena Brehm

Brehm, U. (1983). Strip Möbius triangulasi tripulasi. Proc Amer. Matematika Soc., 89 (3), 519–522. doi: 10.2307 / 2045508

dan beberapa contoh telah mengikuti hasil dari teori matroid.

Tentang perbedaan antara PL dan topologi embeddings, ini hasil dari contoh tandingan umum yang timbul dari Hauptvermutung : Dalam dimensi 5 dan lebih banyak, ada bola topologi yang tidak menerima struktur linear-piecewise

Adakah properti lain yang bisa digeneralisasi? misalnya, dapatkah rumus Euler untuk grafik planar digeneralisasikan ke dimensi yang lebih tinggi?

$k$

Demikian pula, tampaknya 3-hypergraph lengkap pada 6 simpul tidak memiliki 3-embedding sederhana.

Memang, ini hasil dari obstruksi van Kampen-Flores. Ini dijelaskan dengan detail dan kejelasan yang luar biasa dalam buku Matousek Menggunakan Teorema Borsuk Ulam.

Oh oh Anda ingin sangat berhati-hati. Grafik kontak polytopes cembung di 3d dapat mewujudkan grafik apa pun. Anehnya, klik itu dapat direalisasikan oleh n poltop yang diputar dan diterjemahkan salinan dari polytope yang sama (pikiran membingungkan). Lihat makalah ini:

http://www.cs.uiuc.edu/~jeffe/pubs/crum.html

Ini sudah menyiratkan bahwa Anda dapat menyandikan grafik yang cukup jahat sebagai grafik persimpangan segitiga di 3d. Lihat bagian 4 makalah ini:

http://sarielhp.org/p/09/set_cover_hard/

BTW, saya tertarik pada versi yang sama dari masalah Anda dengan mencoba memahami bagaimana grafik persimpangan geometris berperilaku ...

Teorema Schnyder menyatakan bahwa grafik adalah planar jika kemungkinan poset memiliki dimensi paling banyak 3. Ini telah diperluas oleh Mendez ke kompleks kesederhanaan yang sewenang-wenang (lihat "Realisasi Geometris dari Kompleks Kesederhanaan", Gambar Grafik 1999: 323-332). Anehnya ada makalah yang jauh lebih tua dengan judul yang sangat mirip "Realisasi geometris kompleks semi-simplicial", tapi saya curiga bahwa itu pada topik yang berbeda.

Properti yang sangat penting: dualitas selebar pohon.

mis. lihat: Pohon-lebar hiper-grafik dan dualitas permukaan oleh Frederic Mazoit,

Abstraknya adalah sebagai berikut:

Dalam Graph Minors III, Robertson dan Seymour menulis: "Tampaknya lebar pohon dari grafik planar dan lebar pohon dari geometris ganda kira-kira sama, memang, kami telah meyakinkan diri sendiri bahwa mereka berbeda paling banyak satu." Mereka tidak pernah memberikan bukti tentang ini. Dalam makalah ini, kami membuktikan generalisasi dari pernyataan ini untuk menanamkan hypergraph pada permukaan umum, dan kami membuktikan bahwa ikatan kami ketat.

http://www.labri.fr/perso/mazoit/uploads/Surface_duality_journal.pdf