Apakah grafik “gen-terluar-terikat” memiliki treewidth yang konstan?

Biarkan dan dilambangkan dengan G k himpunan semua grafik yang dapat ditanamkan pada permukaan genus k sehingga semua simpul yang terletak di wajah luar . Misalnya, G 0 adalah himpunan grafik outerplanar. Dapatkah treewidth dari grafik di G k harus atas dibatasi oleh beberapa fungsi k ?$k\in\mathbb{N}$$G_k$$k$$G_0$$G_k$$k$

Arah lain jelas tidak berlaku, karena treewidth konstan bahkan tidak menyiratkan genus konstan: Biarkan menjadi penyatuan n salinan terpisah K 3 , 3 . Treewidth H n adalah konstan, genusnya n .$H_n$$n$$K_{3,3}$$H_n$$n$

Iya.

Tambahkan simpul di tengah wajah luar, terhubung ke semua simpul di wajah luar; ini tidak mengubah genus, dan tidak mengurangi treewidth. Sekarang grafik memiliki pohon pencarian pertama yang sangat dangkal yang berakar pada titik baru (semuanya berbatasan dengannya).

Bentuk pohon spanning dari grafik ganda yang ujung-ujung rangkapnya terpisah dari tepi pohon pencarian pertama yang luasnya. Lalu ada satu set tepi O (genus) yang bukan milik salah satu pohon. Masing-masing tepi ini menginduksi siklus pendek (segitiga) bersama dengan jalur di pohon pencarian pertama yang luasnya, dan memotong permukaan di sepanjang siklus ini menghasilkan permukaan planar (lihat makalah saya "Generator dinamis dari grafik yang disematkan secara topologi"). Yaitu, jika G 'adalah subgraf dari grafik input yang disebabkan oleh simpul yang bukan titik akhir dari tepi potong O (genus), maka G' adalah planar, dan simpulnya dapat ditutupi oleh wajah O (genus) dari bagiannya. embedding planar (wajah yang memotong siklus memotong wajah luar asli ke dalam).

Tetapi dalam grafik planar di mana semua simpul milik wajah k, seseorang dapat menghapus tepi O (k) lainnya (pohon spanning dari wajah) untuk mendapatkan grafik planar luar. Jadi treewidth dari G 'adalah O (genus). Jika seseorang membentuk dekomposisi pohon G 'dengan lebar ini, dan kemudian menambahkan setiap kantong simpul yang merupakan titik akhir dari tepi siklus potong, hasilnya adalah dekomposisi pohon dari grafik input asli dengan treewidth O (genus).

Tampaknya ini pasti ada dalam literatur di suatu tempat, tetapi saya tidak tahu di mana dan beberapa pencarian cepat belum berhasil menemukan pernyataan eksplisit dari hasil yang tepat ini. Namun, pernyataan yang lebih umum dalam makalah saya yang berbeda: dalam "Diameter dan treewidth dalam keluarga grafik minor-tertutup" Saya membuktikan di antara hal-hal lain bahwa grafik genus dari diameter terikat telah mengikat treewidth. Dalam hal ini (dengan menambahkan bahwa simpul ekstra dalam wajah luar) diameter dapat dianggap paling banyak dua.