Há algum algoritmos online para testes de planaridade?

Question

Eu sei que planaridade testar pode ser feito em O (v) (equivalentemente O (e ), uma vez que os gráficos planares ter ó (v) os bordos) tempo.

Gostaria de saber se isso pode ser feito on-line em O (1) amortizado tempo que cada aresta é adicionado (O (e) o tempo ainda no geral).

Em outras palavras, em uma tabela de banco de dados que representam arestas de um grafo e sujeito a uma restrição que o gráfico representado é planar, quanto tempo deve o SGBD responsável pela gestão da tomada restrição para validar cada inserção proposta? (Por razões de simplificação, supor que não há deleções.) Deve-lo voltar a executar um do O (v) planaridade testar algoritmos para testar cada inserção proposto ou grupo de inserções?

Answer 1

Depois de um pouco mais investigação parece que a resposta é "sim", há algoritmos on-line, mas "não" não há nenhum com O (1) amortizado tempo de execução.

Aqui está um artigo de 1999, no Journal of the ACM, planaridade totalmente dinâmico testando com aplicações , em que os autores escreveram:

Em particular, considera-se as seguintes três operações sobre um gráfico planar L: (i) inserir uma vantagem se os restos gráfico resultante a planar; (Ii) eliminar um bordo; e (iii) testar se uma vantagem poderia ser adicionado para o gráfico sem violar planaridade. Nós mostramos como para suportar cada uma das operações acima no tempo O (n ^ 2/3), onde n é o número de vértices do gráfico. O limite para testes e deleções é pior caso, enquanto que o limite para inserções é amortizados.

Eu também achei o resumo de um artigo 1989 Incremental planaridade testar reivindicando um o (log n) com destino a inserção de ponta, mas eu não tenho certeza se a sua técnica tampas eliminação também.

O papel de 1999 refere-se também a uma junta (inverso-Ackermann (total de operações, n)) algoritmo para o caso de não deleções, discutido num artigo 1992, planaridade rápido incremento testar , mas CiteSeer é baixo no momento, então eu vou ler a detalhes mais tarde.

Supressão de ser útil ao meu pedido, e ter acesso ao papel J. ACM, eu vou ler mais sobre o O amortizado (n ^ 2/3) estratégia.