Optimally bracing grid frameworks with holes. (English) Zbl 1366.74059
Summary: We consider the bracing problem of a square grid framework possibly with holes and present an efficient algorithm for making the framework infinitesimally rigid by augmenting it with the minimum number of diagonal braces. This number of braces matches the lower bound given by Z. Gáspár et al. [Comput. Assist. Mech. Eng. Sci. 6, No. 3-4, 329–335 (1999; Zbl 1043.74516)]. Our contribution extends the famous result on bracing the rectangular grid framework by E. D. Bolker and H. Crapo [SIAM J. Appl. Math. 36, 473–490 (1979; Zbl 0416.70009)].
The preliminary version has been published in Lect. Notes Comput. Sci. 8881, 474–489 (2014; Zbl 1339.74025).
The preliminary version has been published in Lect. Notes Comput. Sci. 8881, 474–489 (2014; Zbl 1339.74025).
MSC:
| 74P10 | Optimization of other properties in solid mechanics |
| 70C20 | Statics |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 74A05 | Kinematics of deformation |
References:
| [1] | Bolker, E. D.; Crapo, H., Bracing rectangular frameworks. I, SIAM J. Appl. Math., 36, 3, 473-490 (1979) · Zbl 0416.70009 |
| [2] | Gáspár, Z.; Radics, N.; Recski, A., Rigidity of square grids with holes, Comput. Assist. Mech. Eng. Sci., 6, 3-4, 329-335 (1999) · Zbl 1043.74516 |
| [3] | Henneberg, L., Die Graphische Statik der Starren System (1911), Johnson Reprint 1968, Leipzig · JFM 42.0744.10 |
| [4] | Ito, Y.; Kobayashi, Y.; Higashikawa, Y.; Katoh, N.; Poon, S. H.; Saumell, M., Optimally bracing grid frameworks with holes, (Proc. Combinatorial Optimization and Applications: 8th International Conference, vol. 8881. Proc. Combinatorial Optimization and Applications: 8th International Conference, vol. 8881, COCOA 2014 (2014)), 474-489 · Zbl 1339.74025 |
| [5] | Maxwell, J. C., On the calculation of the equilibrium and stiffness of frames, Philos. Mag., 27, 294-299 (1864) |
| [6] | Radics, N.; Recski, A., Applications of combinatorics to statics - rigidity of grids, Discrete Appl. Math., 123, 473-485 (2002) · Zbl 1034.70002 |
| [7] | Whiteley, W., Some matroids from discrete applied geometry, Contemp. Math., 197, 171-313 (1996) · Zbl 0860.05018 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
