# Fast deletion / contraction in combinatorial embedding

I wonder if there is a sublinear algorithm to make deletion or contraction of an edge in a combinatorial embedding of, lets say, planar graph?

Since in combinatorial embedding we have to maintain vertices of G and G* at the same time, taking in account that contraction in the primal is deletion in the dual, it's sufficient only to make deletions, updating primal permutation according to dual and vice-versa. But obvious way to do it is just recompute them, which takes linear time. Can we do any better?

Second question: is there any technique that helps to get rid of multiple edges between same vertices? (the only solution I see to the second problem is to postpone deletion of multiple edges until we will get graph with, for example, m=6n, where m - number of edges, n - number of vertices, this will make time amortized O(1)) Maybe there is some techniques, which can make this time not amortized? (I am also interested in just o(n) solutions, not necessarily O(1))

Thank you very much!

• In second question I meant that we want to get rid of multiple edges while doing contractions and deletions. – Finsky Nov 5 '12 at 16:27

• To summarize the technique in David's paper: Store the cyclic sequence of edges leaving each vertex, in both the primal graph and the dual graph, in a balanced binary tree that supports splits and joins in $O(\log n)$ time (for example, a B-tree, a treap, or a splay tree), instead of a raw linked list. – Jeffε Nov 5 '12 at 17:48