Menghitung Grafik Planar dari Treewidth Terikat

Saya mencari referensi untuk masalah berikut: diberikan bilangan bulat dan , sebutkan semua grafik planar non-isomorfik pada simpul dan treewidth . Saya tertarik pada hasil teoritis dan praktis, tetapi sebagian besar algoritma praktis yang memungkinkan untuk kode dan berjalan untuk nilai dan sebesar mungkin (pikirkan dan ). Jika Anda sudah memiliki jawaban, abaikan ocehan di bawah.k n ≤ k n k k ≤ 5 n ≤ $n$$k$$n$$\leq k$$n$$k$$k \leq 5$$n \leq 15$

Pendekatan berikut berfungsi agak ok untuk menghitung semua grafik non-isomorfik pada simpul dan treewidth (yaitu ketika batasan planaritas dijatuhkan):≤ $n$$\leq k$

(a) Hitung semua grafik non-isomorfik pada simpul dan treewidth .≤ $n-1$$\leq k$

(B) Untuk setiap simpul pada simpul dan treewidth , setiap klik pada simpul dalam dan setiap subset dari tepi dalam , buat dari dengan menambahkan simpul baru berdekatan dengan . Tambahkan ke daftar grahs pada simpul dan treewidth .n - 1 G ′ G - S v C G ′ L n ≤ $G$$n-1$C ≤ k G S $\leq k$$C$$\leq k$$G$$S$$C$$G'$$G - S$$v$$C$$G'$${\cal L}$$n$$\leq k$

(c) Potong dengan menghapus salinan dari grafik yang sama.${\cal L}$

Cara menggoda untuk memperluas ini untuk menghitung grafik planar dari treewidth adalah dengan hanya menyaring grafik non-planar di setiap iterasi. Sayangnya ini gagal untuk menghasilkan semua grafik planar dari treewidth (misalnya karena hanya menyebutkan -degenerate graphs).≤ k $\leq k$$\leq k$$4$

Tentu saja kita dapat menghitung semua grafik pada simpul dan simpul dan hanya kemudian menyaring yang non-planar, tetapi ini gagal untuk mengeksploitasi bahwa kebanyakan grafik adalah non-planar dan tampaknya sangat sub-optimal.≤ $n$$\leq k$

Ada perangkat lunak yang bagus yang menghasilkan grafik planar kecil sehubungan dengan isomorfisme yang mungkin membantu. Seperti yang saya lihat salah satu masalahnya adalah untuk menghasilkan grafik planar non-isomorfik dan sebagian besar grafik planar (pada kurang dari 15 simpul) berukuran kecil.

Untuk memeriksa apakah treewidth mereka lebih kecil dari nilai yang diberikan , salah satu caranya adalah menggunakan algoritma heuristik untuk mempercepat perhitungan ini, hanya dalam kasus algoritma yang tepat tidak praktis. misalnya dalam grafik planar pertama kita dapat menemukan diameter dan jalur sesuai panjang (yang merupakan diameter). Kemudian menemukan titik yang memiliki jarak terpanjang terpendek ( ) untuk setiap vertex lain di antara semua simpul . Treewidth paling banyak , jika ini lebih kecil dariG G P d v ∈ P l u ∈ G ∖ P w ∈ P G d + l $k$$G$$G$$P$$d$$v\in P$$l$$u\in G\setminus P$$w\in P$$G$$d+l$$k$ maka kita selesai jika tidak menerapkan beberapa algoritma heuristik lain atau menjalankan algoritma yang tepat.

Untuk kurang dari 3 grafik yang terhubung, dimungkinkan juga untuk menerapkan heuristik dengan menemukan titik potong dan kemudian memperbaiki titik tersebut dan menemukan lebar pohon dari grafik yang tersisa. Tetapi karena jumlah node kecil ( ) jika grafik terhubung- maka diameternya tidak besar dan saya pikir heuristik pertama harus bekerja di sana. (Saya tidak tahu apakah ada 5 terhubung planar grafik di paling 15 simpul, tapi seperti yang kita tahu tidak ada -connected planar grafik untuk )4 t t > $15$$4$$t$$t>5$

Karena ukuran halangan terbesar untuk lebar pohon tidak diketahui, kita tidak dapat dengan mudah menebak nilai kenaikan dari treewidth dari grafik diberikan . Tetapi tampaknya setidaknya untuk grafik planar seharusnya tidak terlalu besar (orang harus memberikan bukti untuk ini).$k$$G$

Satu dapat menyebutkan semua pasangan mana G adalah grafik planar dengan treewidth paling banyak k , B adalah kantong berukuran k sedemikian sehingga ada dekomposisi pohon G dengan B sebagai kantong.$G,B$$G$$k$$B$$k$$G$$B$

Sekarang untuk setiap pasangan di mana G memiliki n - 1 simpul kita membangun grafik baru G ' untuk setiap himpunan bagian S dari B dengan menambahkan vertex v dengan S sebagai tetangga dan membiarkan B ' menjadi ukuran k subset dari B ∪ v . Menambahkan G ' , B ' jika G ' adalah planar dan tidak isomorfik untuk setiap pasangan yang sudah ditemukan.$G,B$$G$$n-1$$G'$$S$$B$$v$$S$$B'$$k$$B \cup v$$G',B'$$G'$

Batas atas yang mudah pada berapa banyak entri yang perlu disimpan adalah dikalikan jumlah grafik yang disebutkan tetapi ini adalah batas pesimistis. Untuk sebagian besar grafik treewidth k, sebagian besar himpunan bagian ukuran k tidak dapat ba bag, misalnyak×ngrid hanya memilikin⋅3k-1kemungkinan bag.$n \choose k$$k \times n$$n \cdot 3^{k-1}$

Saya percaya ini akan melakukan serta algoritma untuk grafik non planar karena untuk setiap pasangan G, B kita mendapatkan grafik dengan membuat B klik, sebagian besar grafik ini akan menjadi non isomorfik.

Ada beberapa trik yang dapat diterapkan untuk mempercepat ini, saya sarankan melihat ke: http://www.siam.org/meetings/alenex04/abstacts/HBodlaender.pdf