Slider-Pinning Rigidity: a Maxwell–Laman-Type Theorem

1. Brylawski, T.: Constructions. In: White, N. (ed.) Theory of Matroids, Encyclopedia of Mathematics and Its Applications, pp. 127–223. Cambridge University Press, Cambridge (1986)

   Google Scholar 

2. Cox, D.A., Little, J., O’Shea, D.: Ideals, Varieties and Algorithms. Undergraduate Texts in Mathematics, 2nd edn. Springer, New York (1997)

   Google Scholar 

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

   Article  MATH  MathSciNet  Google Scholar 

4. Gluck, H.: Almost all simply connected closed surfaces are rigid. Lect. Notes Math. 438, 225–239 (1975)

   Article  MathSciNet  Google Scholar 

5. Haas, R., Lee, A., Streinu, I., Theran, L.: Characterizing sparse graphs by map decompositions. J. Comb. Math. Comb. Comput. 62, 3–11 (2007)

   MATH  MathSciNet  Google Scholar 

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

   Article  MATH  MathSciNet  Google Scholar 

7. Lee, A., Streinu, I.: Pebble game algorithms and sparse graphs. Discrete Math. 308(8), 1425–1437 (2008). doi:10.1016/j.disc.2007.07.104

   Article  MATH  MathSciNet  Google Scholar 

8. Lee, A., Streinu, I., Theran, L.: Graded sparse graphs and matroids. Journal of Universal Computer Science 13(10) (2007)

9. Lee, A., Streinu, I., Theran, L.: The slider-pinning problem. In: Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG’07) (2007)

10. Lovász, L.: Combinatorial Problems and Exercises, 2nd edn. AMS Chelsea, Providence (2007)

    MATH  Google Scholar 

11. Lovász, L., Yemini, Y.: On generic rigidity in the plane. SIAM J. Algebr. Discrete Methods 3(1), 91–98 (1982)

    Article  MATH  Google Scholar 

12. Lovász, L.: Matroid matching and some applications. J. Comb. Theory, Ser. B 28, 208–236 (1980)

    Article  MATH  Google Scholar 

13. Maxwell, J.C.: On the calculation of the equilibrium and stiffness of frames. Philos. Mag. 27, 294 (1864)

    Google Scholar 

14. Oxley, J.G.: Matroid Theory. Clarendon/Oxford University Press, New York (1992)

    MATH  Google Scholar 

15. Recski, A.: Matroid Theory and Its Applications in Electric Network Theory and in Statics. Springer, Berlin (1989)

    Google Scholar 

16. Saxe, J.B.: Embeddability of weighted graphs in k-space is strongly np-hard. In: Proc. of 17th Allerton Conference in Communications, Control, and Computing, Monticello, IL, pp. 480–489 (1979)

17. Streinu, I., Theran, L.: Sparsity-certifying graph decompositions. Graphs Comb. 25(2), 219–238 (2009). doi:10.1007/s00373-008-0834-4

    Article  MATH  MathSciNet  Google Scholar 

18. Tay, T.S.: A new proof of Laman’s theorem. Graphs Comb. 9, 365–370 (1993)

    Article  MATH  MathSciNet  Google Scholar 

19. Whiteley, W.: The union of matroids and the rigidity of frameworks. SIAM J. Discrete Math. 1(2), 237–255 (1988)

    Article  MATH  MathSciNet  Google Scholar 

20. Whiteley, W.: A matroid on hypergraphs, with applications in scene analysis and geometry. Discrete Comput. Geom. 4, 75–95 (1989)

    Article  MATH  MathSciNet  Google Scholar 

21. Whiteley, W.: Some matroids from discrete applied geometry. In: Bonin, J., Oxley, J.G., Servatius, B. (eds.) Matroid Theory. Contemporary Mathematics, vol. 197, pp. 171–311. American Mathematical Society, Providence (1996)

    Google Scholar 

22. Whiteley, W.: Rigidity and scene analysis. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, pp. 1327–1354. CRC Press, Boca Raton (2004)

    Google Scholar 

Download references