Properti Sesuatu-Treewidth

Mari menjadi parameter grafik (ex. Diameter, jumlah dominasi, dll)$s$

Keluarga dari grafik memiliki properti s -treewidth jika ada fungsi f sehingga untuk setiap grafik G ∈ F , treewidth G paling banyak adalah f ( s ) .$\mathcal{F}$$s$$f$$G\in \mathcal{F}$$G$$f(s)$

Sebagai contoh, misalkan , dan F adalah keluarga dari grafik planar. Maka diketahui bahwa grafik planar dengan diameter paling banyak s memiliki lebar paling banyak O ( s ) . Lebih umum, Eppstein menunjukkan bahwa keluarga grafik memiliki properti diameter-treewidth jika dan hanya jika tidak termasuk beberapa grafik puncak sebagai minor. Contoh keluarga tersebut adalah grafik genus konstan, dll.$s = \mathit{diameter}$$\mathcal{F}$$s$$O(s)$

Sebagai contoh lain, misalkan . Fomin dan Thilikos telah membuktikan hasil analog dengan Eppstein dengan menunjukkan bahwa keluarga grafik memiliki properti dominasi-jumlah-treewidth jika dan hanya jika F memiliki lokal-treewidth. Perhatikan bahwa ini terjadi jika dan hanya jika F memiliki properti diameter-treewidth.$s = \mathit{domination{-}number}$$\mathcal{F}$$\mathcal{F}$

Pertanyaan:

1. Untuk parameter yang grafik adalah s properti -treewidth diketahui ditahan pada grafik planar?$s$$s$
2. Untuk parameter yang grafik adalah s properti -treewidth dikenal berpegang pada grafik dibatasi lokal-treewidth?$s$$s$
3. Apakah ada keluarga grafik lain, tidak sebanding dengan grafik lokal-treewidth terbatas yang dimiliki properti -treewidth untuk beberapa parameter yang sesuai s ?$s$$s$

Saya merasa bahwa pertanyaan-pertanyaan ini ada kaitannya dengan teori bidimensionality . Dalam teori ini, ada beberapa parameter penting. Misalnya, ukuran set umpan balik sudut, penutup sudut, pencocokan maksimal minimum, penutup wajah, set dominasi, set dominasi tepi, set dominasi R, set dominasi terhubung, set dominasi tepi terhubung, set dominasi terkoneksi terhubung, set dominasi R terhubung, dll.

4. $s$$s$

$1$$s(G)$$s(G) \geq s(H)$$H$$G$$s$

$c$$s$$t$$t$$ct^2$

$s$$t$$t$$t$

• ditutup di bawah umur
• sewenang-wenang besar pada t kali t grid untuk t cukup besar

Kemudian s memiliki properti s-treeewidth. Lihat buku kompleksitas parameter baru-baru ini ( http://parameterized-algorithms.mimuw.edu.pl ) di bab treewidth untuk info lebih lanjut.

Di antara daftar Anda, (setidaknya) nomor penutup simpul dan ukuran simpul masukan, untuk grafik secara umum.

1. $s$$\dots$

2. $s$$\dots$