MathDBNP-hardness conjecture for recognizing generic-radii sphere-packing contact graphs
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Sean Dewar, “Identifying contact graphs of sphere packings with generic radii”, arXiv:2302.12588 (2024).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.