Menyematkan grafik sebagai koleksi tetrahedra interior-disjoint

9

Definisikan mesh dalam 3D sebagai kumpulan tetrahedra yang terhubung dengan interior terpisah (jadi tetrahedra hanya berbagi k-face, ). Diberikan grafik yang arbitrer, adakah prosedur yang efisien untuk menguji apakah dapat ditanamkan sebagai sebuah mesh?k≤2

Di sini, penyisipan adalah pemetaan simpul grafik ke titik dalam dan tepi ke garis lurus sehingga ujungnya hanya memotong pada simpul, dan wajah hanya memotong di tepi, dan tidak ada dua wajah yang berpotongan di bagian dalam mereka.R3

ds.algorithms graph-theory Suresh Venkat
sumber
Apakah maksud Anda garis atau segmen garis? Tolong jelaskan dua jenis tepi: wajah berada di tetrahedra dan tepi yang Anda sebutkan ada di grafik ... Anda juga perlu bahwa semua tepi tetrahedral adalah tepi grafik, atau saya hanya akan menyematkan grafik apa pun di grafik lengkap Saya dapatkan dari poin pada kurva momen.
Jack
Maksudku segmen garis, dan ya semua tepi tetrahedral adalah tepi grafik. Saya tidak yakin saya mengerti apa yang Anda maksud dengan 'dua jenis' tepi.
Suresh Venkat
Apakah maksud Anda "Apakah kerangka 1 dari sebuah jaring?" atau "Apakah G sebuah subgraf dari kerangka 1 dari sebuah jaring?" atau sesuatu yang lain? Dari mana datangnya wajah-wajah berdimensi tinggi? GG
Jeffε
@ Jɛ ff E Saya pikir berdasarkan sumber pertanyaan, rendering pertanyaan yang benar adalah "Apakah G kerangka 1 dari sebuah jaring". Tapi saya juga akan tertarik pada kasus ketika G adalah subgraph dari 1-skeleton. Dengan demikian, wajah berdimensi lebih tinggi bukan bagian dari G, tetapi persyaratan bahwa penyisipan jala yang valid membatasi G. Saya harap ini masuk akal.
Suresh Venkat

Jawaban:

4

Dalam Kekerasan embedding kompleks simplicial di Rd disebutkan bahwa setidaknya sekeras mengenali 3-bola, yang diketahui berada di NP, tetapi tidak diketahui berada di P. Mereka terus mengatakan bahwa untuk semua yang kita tahu, masalahnya mungkin tidak dapat dipastikan.EMBED3→3

EDIT: Perbarui. Sebenarnya, jawaban saya berlaku untuk pernikahan PL. Untuk hiasan linear masalahnya diketahui berada di PSPACE. Saya tidak tahu apakah ada yang diketahui.

Shaun Harker
sumber
1
Ah, referensi yang bagus. Saya harus menyelidikinya sedikit lebih hati-hati karena gagasan mereka tentang PL-embeddings mungkin sedikit lebih lemah daripada gagasan yang saya inginkan (yang mereka sebut embedding 'linear'.
Suresh Venkat
Oh begitu. Saya tidak menangkap nuansa itu. Menisik. Yah, semoga bermanfaat sih :)
Shaun Harker