pipette
ENEnglish

Destroying Rigidity in the Plane

Yu Cong, Chao Xu, Yajie Zhao

Preprint

En palabras de los autores

Rigidity and global rigidity are fundamental graph properties in discrete geometry, with applications to structural engineering and network localization. In two dimensions, both admit combinatorial characterizations in terms of the rigidity matroid and graph connectivity. We study the computational complexity of finding minimum-cost sets of edges or vertices whose deletion destroys either property in a finite simple graph. With unit costs, we give deterministic polynomial-time algorithms for edge deletion destroying global rigidity and vertex deletion destroying either property. We prove that edge deletion destroying rigidity is NP-hard and that, with positive integer costs, all four problems are NP-hard. These results resolve, in dimension two, the open questions on recognizing robustness under edge and vertex deletions posed by Jord\'an and Whiteley (2017), as well as the minimum edge-deletion problem for rigidity recorded in EGRES Open.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.