Skip to main content
Log in

Augmenting the Rigidity of a Graph in R 2

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

Given a Laman graph G, i.e. a minimally rigid graph in R 2, we provide a Θ(n 2) algorithm to augment G to a redundantly rigid graph, by adding a minimum number of edges. Moreover, we prove that this problem of augmenting is NP-hard for an arbitrary rigid graph G in R 2.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bang-Jensen, J., Gabow, H., Szigeti, Z., Jordán, T.: Edge-connectivity augmentation with partition constraints. SIAM J. Discrete Math. 12, 160–207 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  2. Berg, A., Jordán, T.: A proof of Connelly’s conjecture on 3-connected circuits of the rigidity matroid. J. Comb. Theory, Ser. B 88, 77–97 (2003)

    Article  MATH  Google Scholar 

  3. Berg, A., Jordán, T.: Algorithms for graph rigidity and scene analysis. In: Lecture Notes in Comput. Sci., vol. 2832, pp. 78–89. Springer, Berlin (2003)

    Google Scholar 

  4. Eren, T., Anderson, B., Morse, A., Whiteley, W., Belhumeur, P.: Operations on rigid formations of autonomous agents. Commun. Inf. Syst. 3, 223–258 (2004)

    MathSciNet  Google Scholar 

  5. Eswaran, K.P., Tarjan, R.E.: Augmentation problems. SIAM J. Comput. 5, 653–665 (1976)

    Article  MATH  MathSciNet  Google Scholar 

  6. Fekete, Z.: Source location with rigidity and tree packing requirements. Oper. Res. Lett. 34, 607–612 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  7. Fekete, Z., Jordán, T.: Rigid realizations of graphs on small grids. Comput. Geom. 32, 216–222 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  8. Fekete, Z., Jordán, T.: Uniquely localizable networks with few anchors. In: Lecture Notes in Comput. Sci., vol. 4240, pp. 176–183. Springer, Berlin (2006)

    Google Scholar 

  9. Fekete, Z., Jordán, T., Whiteley, W.: An inductive construction for plane Laman graphs via vertex splitting. In: Lecture Notes in Comput. Sci., vol. 3221, pp. 299–310. Springer, Berlin (2004)

    Google Scholar 

  10. Frank, A. (ed.): Connectivity augmentation of networks: structures and algorithms. Math. Program. 84(3), 439–640 (1999)

  11. Gabow, H., Jordán, T.: Incrementing bipartite digraph edge-connectivity. J. Comb. Opt. 4, 449–486 (2000)

    Article  MATH  Google Scholar 

  12. Garey, M.R., Johnson, D.S.: Computers and Intractability. Freeman, San Francisco (1979)

    MATH  Google Scholar 

  13. Gluck, H.: Almost all simply connected closed surfaces are rigid. In: Lecture Notes in Math., vol. 438, pp. 225–239. Springer, Berlin (1975)

    Google Scholar 

  14. Graver, J., Servatius, B., Servatius, H.: Combinatorial Rigidity. Graduate Studies in Mathematics, vol. 2. Am. Math. Soc., Providence (1993)

    MATH  Google Scholar 

  15. Haas, R., Orden, D., Rote, G., Santos, F., Servatius, B., Servatius, H., Souvaine, D., Streinu, I., Whiteley, W.: Planar minimally rigid graphs and pseudo-triangulations. Comput. Geom. 31(1–2), 31–61 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  16. Hendrickson, B.: Conditions for unique graph realizations. SIAM J. Comput. 21(1), 65–84 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  17. Henneberg, L.: Die graphische Statik der starren Systeme. Leipzig 1911, Johnson Reprint (1968)

  18. Hsu, T.S.: On four-connecting a triconnected graph. In: Proc. 33rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 70–79 (1992)

  19. Jackson, B., Jordán, T.: Connected rigidity matroids and unique realizations of graphs. J. Comb. Theory, Ser. B 94, 1–29 (2005)

    Article  MATH  Google Scholar 

  20. Jacobs, D.J., Hendrickson, B.: An algorithm for two-dimensional rigidity percolation: the pebble game. J. Comput. Phys. 137, 346–465 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  21. Kant, G.: Augmenting outerplanar graphs. J. Algorithms 21, 1–25 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  22. Laman, G.: On graphs and rigidity of plane skeletal structures. J. Eng. Math. 4, 331–340 (1970)

    Article  MATH  MathSciNet  Google Scholar 

  23. Lee, A., Streinu, I.: Pebble game algorithms and (k,l)-sparse graphs. In: EuroComb 2005, DMTCS Proc. AE 2005, pp. 181–186 (2005)

  24. Lee, A., Streinu, I., Theran, L.: Finding and maintaining rigid components. In: Proceedings of the 17th Canadian Conference on Computational Geometry, CCCG’05, pp. 219–222 (2005)

  25. Mourzakel, C.: An efficient algorithm for testing the generic rigidity of graphs in the plane. J. Phys. A 29(24), 8079–8098 (1996)

    MathSciNet  Google Scholar 

  26. Olfati-Saber, R., Murray, R.M.: Graph rigidity and distributed formation stabilization of multi-vehicle systems. In: Proc. of the 41st Conference on Decision and Control, Las Vegas, NV, December 2002

  27. Recski, A.: Matroid Theory and Its Applications. Springer, New York (1989)

    Google Scholar 

  28. Servatius, B.: Birigidity in the plane. SIAM J. Discrete Math. 2(4), 582–589 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  29. Streinu, I.: Pseudo-triangulations, rigidity and motion planning. Discrete Comput. Geom. 34, 587–635 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  30. Sugihara, K.: On some problems in the design of plane skeletal structures. SIAM J. Algorithms Discrete Methods 4(3), 355–362 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  31. Thorpe, M.F., Duxbury, P.M. (eds.): Rigidity Theory and Applications. Kluwer Academic, Dordrecht (1999)

    Google Scholar 

  32. Watanabe, T., Nakamura, A.: Edge-connectivity augmentation problems. J. Comput. Syst. Sci. 35, 96–144 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  33. Watanabe, T., Nakamura, A.: A smallest augmentation to 3-connect a graph. Discrete Appl. Math. 28, 183–186 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  34. Whiteley, W.: Rigidity and scene analysis. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn., pp. 1327–1354 (2004)

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to J. Tejel.

Additional information

Partially supported by Aragón Government under grant E58-DGA and MEC MTM2006-01267.

Rights and permissions

Reprints and permissions

About this article

Cite this article

García, A., Tejel, J. Augmenting the Rigidity of a Graph in R 2 . Algorithmica 59, 145–168 (2011). https://doi.org/10.1007/s00453-009-9300-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-009-9300-9

Keywords

Navigation