Pertanyaan ref pemisah planar lain

Apakah ada di antara Anda yang tahu referensi untuk hasil berikut (secara mengejutkan membosankan untuk dibuktikan)?

Diberikan graf planar terhubung dengan simpul dan tepi , ia memiliki pemisah simpul ukuran $G$ $n$ $n+t$ . $O( \sqrt{t}+1)$

reference-request planar-graphs separation Sariel Har-Peled
sumber

Apakah ini benar-benar membosankan? Anda memiliki paling banyak

blok, kontrak mereka menjadi simpul dan gunakan teorema pemisah tertimbang untuk mereka. Jika blok pemisah berukuran besar, Anda dapat terus menghancurkan semua

t

$t$

tepi di antara mereka dan kemudian pisahkan masing-masing dengan dua simpul masing-masing.

O (\sqrt{t})

$O(\sqrt t)$

domotorp

Apa definisi yang tepat dari blok?

Sariel Har-Peled

Apakah Anda benar-benar membutuhkan

dalam

+ 1

$+1$

O (\cdot)

$O(\cdot)$

Aryeh

Iya. Jika t adalah nol ....

Sariel Har-Peled

@domotorp BTW, saya tidak berpikir ide Anda bekerja - seluruh grafik mungkin menjadi satu blok - hanya berpikir tentang jalan, dan tepi tambahan yang menghubungkan dua titik akhir, dan mereka beberapa t tepi lainnya ...

Sariel Har-Peled

Jawaban:

Berikut ini adalah bukti menggunakan palu yang terkenal.

$G$ $t+1$ $G$ $t+1$

$G$ $O(\sqrt{t})$ $k$ $G$ $G$ $\Omega(k)$ $\Omega(k)$ $\Omega(k^2)$ $t+1$ $k = O(\sqrt{t})$

Chandra Chekuri
sumber

G

$G$

t

$t$

G

$G$

O (\sqrt{t})

$O(\sqrt{t})$

Teorema dikutip dari Robertson Seymour Thomas memiliki mandiri bukti yang relatif singkat, sehingga tidak seperti palu besar.

daniello

Diedit untuk menghapus "besar" tetapi tetap "palu".

Chandra Chekuri

@aniello bukankah itu grafik minor V?

Saeed