Algum de vocês conhece uma referência para o seguinte resultado (surpreendentemente tedioso para provar)?
Dado um gráfico plano conectado com n vértices e n + t arestas, ele possui um separador de vértices de tamanho O ( √.
reference-request
planar-graphs
separation
Sariel Har-Peled
fonte
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 O ( √)
arestas entre elas e depois se separam arbitrariamente com dois vértices cada.
domotorp 12/07/19
Qual é a definição exata dos blocos?
Sariel Har-Peled
1
Você realmente precisa do dentro do O ( ⋅ ) ?
Aryeh
2
Sim. Se t é zero ...
Sariel Har-Peled
2
@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