Take the 2-minute tour ×

This is a question about an algorithm to solve a graph theory problem.

Let us say we are given two generically globally rigid graphs F1 and F2. We also have a list E of edges that connect vertex pairs (i,j), where i is always a vertex in F1 and j is always a vertex in F2. Eren et al. (see citation below) proved that, in two dimensions, the graph F created by merging F1, F2 and E is also generically globally rigid if the following two conditions are satisfied:

  1. E contains at least three distinct vertices in F1, and at least three distinct vertices in F2.
  2. There are at least four edges in E.

It is relatively straightforward to check that the above two conditions hold, for any given F1, F2 and E. What I am interested in is providing a fix for the case where the above conditions are not satisfied. Specifically, I'm looking for an algorithm to find the smallest set of new edges E' that, when merged with E, satisfy the conditions above. Does anybody have an idea on how I should go about doing this?

I have given the problem a stab, and I know how to check whether F1 and F2 meet Condition (1). I am then able to randomly select new vertices from each graph to use in E+E'. What I'm stuck on is how to decide on the connectivity between the new and old vertices.

Citation (Eren et al.) http://www.cs.columbia.edu/techreports/cucs-022-05.pdf

share|improve this question
Check out cstheory.stackexchange.com –  cyborg Jan 25 '12 at 20:31

1 Answer 1

up vote 0 down vote accepted

I think you should just be able to

  • Pick some arbitrary sets of vertices V1 and V2 (not incident to any edge in E, of course) until we have enough to satisfy (1)
  • Pair off elements of V1 and V2 to form edges in E' until one set is exhausted
  • Connect the remainder to arbitrary vertices in the opposite set
  • Throw in one more arbitrary edge between F1 and F2 if E+E' still doesn't satisfy (2)
share|improve this answer
I think that your approach will satisfy the merge conditions, but I'm not sure that this approach will result in the smallest E'. –  Andrew Jan 25 '12 at 15:18
It seems from your original post that you're satisfied with the first step (selecting V1 and V2). Given V1 and V2, we must add at least max{|V1|,|V2|} edges, or we'll leave some vertex without an edge. This approach gives |E'|=max{|V1|,|V2|} (assuming we don't need to pad it out for the sake of condition (2)), so it can't get any smaller. –  Nick Barnes Jan 25 '12 at 19:49
Hi Nick. Thank you for taking the time to explain that. Having explained it in the way that you did, it appears as if the problem it much easier to solve than I had first anticipated! –  Andrew Jan 26 '12 at 11:35

Your Answer


