Sparse Incidence Geometries and Pebble Game Algorithms
From MaRDI portal
Publication:6510482
arXiv2306.05050MaRDI QIDQ6510482FDOQ6510482
Authors: Signe Lundqvist, Tovohery Hajatiana Randrianarisoa, Klara Stokes, Joannes Vermant 
Abstract: In this paper we define sparsity and tightness of rank 2 incidence geometries, and we develop an algorithm which recognises these properties. We give examples from rigidity theory where such sparsity conditions are of interest. Under certain conditions, this algorithm also allows us to find a maximum size subgeometry which is tight. This work builds on so-called pebble game algorithms for graphs and hypergraphs. The main difference compared to the previously studied hypergraph case is that in this paper, the sparsity and tightness are defined in terms of incidences, and not in terms of edges. This difference makes our algorithm work not only for uniform hypergraphs, but for all hypergraphs.
Rigidity and flexibility of structures (aspects of discrete geometry) (52C25) Computational methods for problems pertaining to convex and discrete geometry (52-08)
This page was built for publication: Sparse Incidence Geometries and Pebble Game Algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6510482)
