Apa algoritma polinomial paling sederhana untuk PLANARITY?

28

Ada beberapa algoritma yang memutuskan dalam waktu polinomial apakah grafik dapat digambar di pesawat atau tidak, bahkan banyak dengan waktu berjalan linier. Namun, saya tidak dapat menemukan algoritma yang sangat sederhana yang dapat dengan mudah dan cepat dijelaskan di kelas dan akan menunjukkan bahwa PLANARITY dalam P. Apakah Anda tahu?

Jika perlu, Anda dapat menggunakan teorema Kuratowski atau Fary tetapi tidak ada hal yang dalam, seperti teorema minor graph. Perhatikan juga bahwa saya tidak peduli dengan waktu yang berjalan, saya hanya ingin sesuatu yang jumlahnya banyak.

Di bawah ini adalah 3 algoritma terbaik sejauh ini, yang menunjukkan trade-off kesederhanaan / tanpa teori yang dibutuhkan.

Algoritma 1: Dengan menggunakan itu kita dapat memeriksa apakah grafik berisi atau sebagai minor dalam waktu polinomial, kita mendapatkan algoritma yang sangat sederhana menggunakan teori yang mendalam. (Perhatikan bahwa teori ini sudah menggunakan embedding grafik, seperti yang ditunjukkan oleh Saeed, jadi ini bukan pendekatan algoritmik yang nyata, hanya sesuatu yang sederhana untuk memberi tahu siswa yang sudah tahu / menerima teorema minor graph.)K 3 , 3K5K3,3

Algoritma 2 [berdasarkan jawaban seseorang]: Sangat mudah untuk melihat bahwa itu cukup untuk berurusan dengan 3-terhubung grafik. Untuk ini, cari wajah dan kemudian menerapkan teorema musim semi Tutte.

Algoritma 3 [direkomendasikan oleh Juho]: Algoritma Demoucron, Malgrange dan Pertuiset (DMP). Gambarlah sebuah siklus, komponen dari grafik yang tersisa disebut fragmen, kami menanamkannya dengan cara yang sesuai (sementara itu membuat fragmen baru). Pendekatan ini tidak menggunakan teorema lain.

graph-algorithms co.combinatorics planar-graphs domotorp
sumber
1
Saya pikir banyak yang setuju algoritma waktu polinomial paling sederhana adalah algoritma Demoucron, Malgrange dan Pertuiset (DMP). Ini adalah buku teks algoritma yang biasanya mencakup (lihat misalnya Gibbons 1985 atau Bondy & Murty 1976). Apakah itu cukup dengan hanya memutuskan planaritas, atau haruskah algoritma juga menghasilkan embedding planar? IIRC, makalah SODA'99 tentang Boyer dan Myrvold @joro mungkin merujuk pada meninggalkan rincian, terutama mengenai kompleksitas waktu.
Juho
2
Jika Anda hanya ingin masalah keputusan IS PLANAR, bukankah dua anak di bawah umur terlarang yang keberadaannya dapat diperiksa dalam waktu polinomial cukup?
joro
2
@ joro: Ya, tentu saja itu akan menjadi solusi yang sederhana tapi saya lebih suka menghindari menggunakan teorema yang kuat.
domotorp
1
Algoritma yang saya sebutkan pada dasarnya adalah algoritma Auslander-Parter. Masalah dalam algoritme saya adalah bagian 7 ketika saya mengatakan kami dapat membuat grafik dua komponen. Kita bisa dalam algoritma asli tetapi dalam algoritma yang saya katakan kita perlu definisi komponen yang lebih tepat dan itu keluar dari keinginan saya untuk menjelaskannya secara rinci. Bagian rekursif jelas benar (jika kita bisa melakukan langkah 7 maka kita selesai), di mana Anda ragu tentang kebenarannya. Saya tidak memperbarui jawaban saya karena saya melihat sekitar dua halaman dan saya tidak dapat menyingkatnya lagi dan itu tidak baik untuk menyebutnya sederhana.
Saeed
3
Mengurangi menjadi kasus 3-terhubung adalah sederhana secara konseptual dan harus dijelaskan dalam hal apa pun. Jika kita tidak terlalu tertarik pada pengurangan efisiensi menjadi case yang terhubung 3 dapat dengan mudah dilakukan. Periksa semua potongan 2 simpul.
Chandra Chekuri

Jawaban:

6

Saya akan menjelaskan suatu algoritma. Saya tidak yakin itu memenuhi syarat "mudah" dan beberapa buktinya tidak begitu mudah.

Pertama kita memecah grafik menjadi 3 komponen yang terhubung, seperti yang disebutkan oleh Chandra Chekuri.

  1. Pisahkan grafik menjadi komponen yang terhubung.
  2. Pecah setiap komponen yang terhubung menjadi 2 komponen yang terhubung. Hal ini dapat dilakukan dalam pemeriksaan waktu polinomial untuk setiap titik dari setiap komponen yang terhubung 2 G i apakah G i - v terhubung.vGiGi−v
  3. Hancurkan setiap komponen yang terhubung 2 menjadi komponen yang terhubung. Ini dapat dilakukan dalam waktu polinomial memeriksa dua simpul berbeda dari masing-masing komponen 2-terhubung G i apakah G i - { v , u } terhubung.v,uGiGi−{v,u}

Kami telah mengurangi masalah untuk memeriksa apakah komponen 3-terhubung dari grafik adalah planar. Biarkan menunjukkan komponen 3-terhubung.G

  1. Mengambil siklus dari G .CG
  2. Sematkan simpul sebagai simpul dari poligon cembung. Letakkan masing-masing simpul lainnya di pusat barisan tetangganya. Ini mengarah ke sistem persamaan linear yang memberitahu koordinat masing-masing dhuwur. Biarkan D menjadi gambar yang dihasilkan; mungkin ada penyeberangan.CD
  3. Jika tidak memiliki persimpangan, kami selesai.D
  4. Ambil simpul dalam komponen G - V ( C ) yang terhubung . Pembatasan D ke subgraph yang diinduksi G [ U ∪ V ( C ) ] harus planar. Kalau tidak, G bukan planar. Ambil wajah setiap F pada gambar D terbatas pada subgraf diinduksi G [ U ∪ V ( C ) ] , dan biarkan C ' menjadi siklus mendefinisikan F . Jika GUG−V(C)DG[U∪V(C)]GFDG[U∪V(C)]C′FGharus planar, maka harus menjadi siklus wajah. (Ketika C adalah siklus Hamilton, maka C ′ harus dibangun menggunakan tepi.)C′CC′
  5. Ulangi langkah 2 dengan C 'alih-alih C. Jika gambar yang dihasilkan adalah planar, maka adalah planar. Lain G tidak planar.GG

Komentar:

  • Berdebat bahwa musim semi Tutte's embedding memberikan planar embedding tidak mudah. Saya menyukai presentasi dalam buku Edelsbrunner dan Harer, Topologi Komputasi, tetapi itu hanya untuk triangulasi. Colin de Verdiere membahas penanaman musim semi di http://www.di.ens.fr/~colin/cours/algo-graphs-surfaces.pdf , bagian 1.4. Referensi umum adalah Linial, Lovász, Wigderson: Karet gelang, pita cembung dan konektivitas grafik. Combinatorica 8 (1): 91-102 (1988).
  • Memecahkan sistem persamaan linear dalam jumlah poliomial operasi aritmatika mudah dilakukan melalui eliminasi Gaussian. Memecahkannya menggunakan jumlah bit yang tidak mudah.
some one
sumber
Saya mengedit jawaban untuk menghindari penggunaan jembatan dan grafik yang tumpang tindih.
seseorang
Misalkan setiap komponen 3-terhubung dapat disematkan. Lalu apa yang bisa kita simpulkan tentang grafik asli? Menggunakan grafik yang terhubung 3 memiliki (paling banyak) satu embedding, mungkin kita bisa menyelesaikannya dari sini, tetapi langkah ini juga harus dilakukan.
domotorp
Pada akhirnya, pada langkah 4, apa wajah dalam gambar non-planar? Saya kira ini masih dapat didefinisikan secara alami. Dan pada akhirnya, "Lain G bukan planar" memang tampak cukup sepele.
domotorp
DG[U∪V(C)]G
Dalam hal ini kami setuju, tetapi saya tidak melihat bagaimana ini membantu.
domotorp
3

Algoritma Boyer dan Myrvold dianggap sebagai salah satu algoritma pengujian planaritas canggih

Di Ujung Tombak: Sederhana O (n) Planaritas oleh Edge Addition oleh Boyer dan Myrvold.

Bab buku ini mensurvei banyak algoritma pengujian planaritas dan mudah-mudahan Anda menemukan algoritma yang cukup sederhana.

Mohammad Al-Turkistany
sumber
Saya tidak tertarik pada ujung tombak dari algoritma planaritas, saya ingin sesuatu yang mudah dijelaskan. Saya tidak dapat menemukan sesuatu yang lebih sederhana daripada algoritma Demoucron, Malgrange dan Pertuiset (DMP) dalam buku ini.
domotorp
0

Bagaimana dengan algoritma Hopcroft dan Tarjan 1974 {1} ?

{1} Hopcroft, John, dan Robert Tarjan. "Pengujian planaritas yang efisien." Jurnal ACM (JACM) 21.4 (1974): 549-568.

Ari Trachtenberg
sumber
Ini adalah algoritma yang cepat dan bukan sederhana.
domotorp
0

Dua algoritma, keduanya di LogSpace

  1. Eric Allender dan Meena Mahajan - Kompleksitas Pengujian Planaritas
  2. Samir Datta dan Gautam Prakriya - Pengujian Planaritas Kembali

Yang kedua jauh lebih sederhana dari yang pertama.

Anonim
sumber
Tidak sederhana sama sekali.
domotorp