Identifying contact graphs of sphere packings with generic radii

MaRDI QIDQ6508941arXivFDO

Authors Sean Dewar

Mathematics Subject Classification ID

Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Combinatorial aspects of packing and covering (05B40) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25)

Abstract: Ozkan et al. conjectured that any packing of $n$ spheres with generic radii will be stress-free, and hence will have at most $3n-6$ contacts. In this paper we prove that this conjecture is true for any sphere packing with contact graph of the form $Goplus{K}_2$, i.e., the graph formed by connecting every vertex in a graph $G$ to every vertex in the complete graph with two vertices. We also prove the converse of the conjecture holds in this special case: specifically, a graph $Goplus{K}_2$ is the contact graph of a generic radii sphere packing if and only if $G$ is a penny graph with no cycles. This result proves that the problem of determining whether a graph is the contact graph of a generic radii sphere packing is NP-Hard.

This page was built for publication: Identifying contact graphs of sphere packings with generic radii

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6508941)