Exclusão / contração rápida na incorporação combinatória

Gostaria de saber se existe um algoritmo sublinear para excluir ou contrar uma aresta em uma incorporação combinatória de, digamos, gráfico planar?

Como na incorporação combinatória, temos que manter os vértices de G e G * ao mesmo tempo, levando em consideração que a contração no primal é a exclusão no dual, basta apenas fazer deleções, atualizando a permutação primordial de acordo com dual e vice-versa . Mas a maneira óbvia de fazer isso é apenas recalculá-los, o que leva tempo linear. Podemos fazer melhor?

Segunda pergunta : existe alguma técnica que ajude a se livrar de múltiplas arestas entre os mesmos vértices? (a única solução que vejo para o segundo problema é adiar a exclusão de várias arestas até obtermos um gráfico com, por exemplo, m = 6n, onde m - número de arestas, n - número de vértices, isso fará com que o tempo seja amortizado O (1)) Talvez haja algumas técnicas, que podem tornar esse tempo não amortizado? (Também estou interessado em apenas o (n) soluções, não necessariamente O (1))

Muito obrigado!

Esta pergunta está incompleta sem especificar quais informações sobre o gráfico, conforme ele muda, você deseja que sua estrutura de dados do gráfico dinâmico produza ou suporte consultas. Mas o artigo a seguir é provavelmente relevante, embora seja descrito em um cenário mais geral de incorporações combinatórias em gênero arbitrário, em vez de apenas plano. Definitivamente, suporta contrações e exclusões, bem como suas operações reversas, em tempo logarítmico por operação.

Geradores dinâmicos de gráficos topologicamente incorporados. D. Eppstein. arXiv: cs.DS / 0207082 . SODA 2003, pp. 599-608.

Quanto à segunda pergunta: não vejo como lidar com várias adjacências em geral, mas é fácil livrar-se dos bigons (várias arestas sem nada entre elas), pois eles só podem vir das duas faces de ambos os lados. uma aresta contraída ou da face que circunda uma aresta excluída. Isso deve ser suficiente para muitos propósitos, uma vez que se livrar dos bigons garante que o gráfico restante tenha um número de arestas proporcional ao número de vértices.