Outra pergunta ref de separador planar

Algum de vocês conhece uma referência para o seguinte resultado (surpreendentemente tedioso para provar)?

Dado um gráfico plano conectado com vértices e arestas, ele possui um separador de vértices de tamanho $G$ $n$ $n+t$ . $O( \sqrt{t}+1)$

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

É realmente tão entediante? Você tem no máximo

blocos, contrai-os em vértices e usa o teorema do separador ponderado para eles. Caso os blocos de separação sejam grandes, você pode destruir todos os

t

$t$

arestas entre elas e depois se separam arbitrariamente com dois vértices cada.

O (\sqrt{t})

$O(\sqrt t)$

domotorp 12/07/19

Qual é a definição exata dos blocos?

Sariel Har-Peled

Você realmente precisa do

dentro do

+ 1

$+1$

O (\cdot)

$O(\cdot)$

Aryeh

Sim. Se t é zero ...

Sariel Har-Peled

@domotorp BTW, eu não acho que sua ideia funcione - todo o gráfico pode ser um único bloco - pense apenas em um caminho e em uma borda adicional conectando os dois pontos de extremidade e outras bordas ...

Sariel Har-Peled

Respostas:

Aqui está uma prova usando um martelo conhecido.

$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
fonte

G

$G$

t

$t$

G

$G$

O (\sqrt{t})

$O(\sqrt{t})$

O teorema citado de Robertson Seymour Thomas tem uma prova independente relativamente curta, portanto não é um martelo tão grande.

Daniello

Editado para remover "grande" mas retido "martelo".

Chandra Chekuri

@daniello não é esse gráfico menor V?

Saeed