Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
In second question I meant that we want to get rid of multiple edges while doing contractions and deletions. – Sergey Finsky Nov 5 '12 at 16:27
up vote 10 down vote accepted

This question is incomplete without specifying what information about the graph as it changes you want your dynamic graph data structure to output or support queries for. But the following paper is likely relevant, even though it is described in a more general setting of combinatorial embeddings in arbitrary genus rather than just planar. It definitely supports both contractions and deletions, as well as their reverse operations, in logarithmic time per operation.

Dynamic generators of topologically embedded graphs. D. Eppstein. arXiv:cs.DS/0207082. SODA 2003, pp. 599-608.

As for the second question: I don't see how to handle multiple adjacencies in general, but it's easy to get rid of bigons (multiple edges with nothing between them) as they can only come from the two faces that are on either side of a contracted edge or from the face that surrounds a deleted edge. That should be sufficient for many purposes since getting rid of the bigons ensures that the remaining graph has a number of edges proportional to its number of vertices.

share|cite|improve this answer
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. – JɛffE Nov 5 '12 at 17:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.