NP-hardness conjecture for recognizing generic-radii sphere-packing contact graphs
A graph is a generic-radii sphere-packing contact graph if it is the contact graph of a sphere packing whose radii are generic. NP-hardness conjecture. Determining whether a graph is a generic-radii sphere-packing contact graph is NP-hard. The question is connected to recognizing penny graphs, and the source notes evidence for related NP-hardness results, but the stated problem remains unresolved.
References
Primary source
Sean Dewar, “Identifying contact graphs of sphere packings with generic radii”, arXiv:2302.12588 (2024).
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.