Three-dimensional sphere packing from a planar height function

Definitions and mathematical statement

Let a circle packing of a planar graph $G=(V,E)$ in ${\mathbb{R}}^2$ have disks with centers $z_v$, pairwise disjoint interiors, and tangency graph $G$. Let $f:V\to{\mathbb{Z}}$ satisfy \[ |f(v)-f(w)|\leq1\qquad(\{v,w\}\in E). \] For each vertex $v$, the proposed construction chooses a Euclidean-nearest vertex of strictly lower height: \[ u_v\in\operatorname*{arg\,min}_{u:\ f(u)<f(v)}|z_u-z_v|, \qquad E'=E\cup\{\{v,u_v\}:v\in V\}. \] The new edges join to lower vertices anywhere in $V$, not only to original neighbors. Their orientation is ignored for the resulting undirected graph.

The question is whether the resulting graph $(V,E')$ is the exact tangency graph of a sphere packing in ${\mathbb{R}}^3$: there should exist closed balls of positive radii with disjoint interiors, indexed by $V$, such that two balls are tangent if and only if their indices form an edge of $E'$. No prescribed three-dimensional centers, unit radii, or vertical lifting of the given packing is required by the excerpt.

The construction is undefined when a vertex has no lower vertex; every nonempty finite height-labeled graph has a global minimum. One possible convention is to add no edge at such a vertex, but that convention is not supplied and requires confirmation. On an infinite packing a nearest lower vertex need not exist without additional assumptions, and ties also need a rule. It is not stated whether all choices or some choices must yield a sphere-packable graph. The Euclidean distance is interpreted between the packing centers, the usual embedded-vertex convention, rather than between disk boundaries.

Short English statement

Add to each vertex of a circle-packed graph an edge to its nearest lower-height vertex, for an integer height function changing by at most one along original edges. Must the augmented graph be sphere-packable in three dimensions? Vertices with no lower target, ties, and infinite-packing minima need conventions.

Sources

• Local UnsolvedMath registry, permanent ID 10000030, source code catalogue entry; Itai Benjamini; no proposal year supplied; updated 2026-08-06.
• Benjamini, Coarse Geometry and Randomness, Saint-Flour notes, Open problem 6.8, PDF page 53: https://www.wisdom.weizmann.ac.il/~itai/stflouraug24.pdf#page=53. Supplied archive: https://arquivo.pt/noFrame/replay/20201231041548id_/http://www.wisdom.weizmann.ac.il/~itai/stflouraug24.pdf. Registry access date 2026-07-29; text extraction checked against rendered PDF, as reported in provenance. Item retained after deduplication and source-side review, with no complete resolution found in the bounded audit. Current status and release reuse terms require review.
• The supplied summary gives no additional primary reference or resolution.