8
$\begingroup$

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!

Improve this question
$\endgroup$
1
  • $\begingroup$ In second question I meant that we want to get rid of multiple edges while doing contractions and deletions. $\endgroup$
    – user197284
    Nov 5, 2012 at 16:27

1 Answer 1

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jeffε
    Nov 5, 2012 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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