Consider $n$ circles with variable radii $r_1,\ldots, r_n$ that pack inside a fixed circle of unit radius. In other words, all $n$ variable-radius circles are contained in the unit radius circle and their interiors have empty intersections. The tangency graph of a packing comprises $n+1$ vertices, one for each circle, and edges between vertices if the corresponding circles are tangent.
Conjecture: in a packing that maximizes $r_1+\cdots +r_n$, the corresponding tangency graph is planar and triangulated.
This conjecture looks like it might be related to the Koebe-Andreev-Thurston circle packing theorem. The latter states that for every planar triangulated graph there is a corresponding circle packing of the kind described and that this packing is unique up to conformal transformations. While it may turn out that the KAT theorem can provide some insights on proving the conjecture, I believe that something else is going on. For instance, the radius-sum objective function is not conformally invariant.
I have good numerical evidence in support of this conjecture. The optimum configurations I've found up to $n=20$ all have triangulated graphs. I'm posting this on MO because I also have something that looks like it may be "close" to a proof. Perhaps someone can close the gap or convince me that the gap is actually a bottomless chasm -- either would be helpful!
Here is my proof strategy:
Use convexity to show that an optimal configuration maximizes the number of edges in the tangency graph.
Use Euler's theorem to show that a tangency graph that maximizes the number of edges is triangulated.
This is a constrained optimization problem in $\mathbb{R}^{3n}$. Consider the constraint that applies to circles 1 and 2: $(x_1-x_2)^2+(y_1-y_2)^2 \ge (r_1+r_2)^2$. This type of constraint is called "reverse convex" (the feasible region is the complement of an open convex set). Feasible regions in reverse convex problems (intersection of open set complements) can be quite complex -- they may not even be connected. On the other hand, they have a very nice property when we are maximizing a convex function: an optimum can always be found at a "vertex" of the feasible region. In a reverse convex problem in $\mathbb{R}^{N}$, a vertex is a point of the feasible region where at least $N$ of the constraints are equalities. We can think of reverse convex problems as generalizing linear programming in a way that inherits all the nice local properties.
The existence of a global optimizer requires that the feasible region is non-empty and compact. This is not an issue for the circle packing problem since we can let the radii range over all the real numbers and add reverse convex constraints $r_1\ge 0,\ldots,r_n\ge 0$.
The alert reader will already have realized that not all of the constraints in the circle packing problem are reverse convex! The constraints that apply to the fixed unit circle have the wrong sense of the inequality, e.g. $x_1^2 + y_1^2 \le (1-r_1)^2$. One can try to fix this problem by replacing the fixed unit circle with a regular $M$-gon and taking the limit (in some sense) of large $M$. This has two nice consequences. First, the optimization is now truly reverse convex (half-plane constraint for every side of the polygon) and so there is an optimizer where exactly $3n$ constraints are active (at their equality value). To see the second nice feature we have to do some counting.
The tangency graph has one new feature when the fixed circle is replaced by a regular $M$-gon: it is no longer simple because it may have doubled edges between the variable-radius circles and the polygon (whenever a circle is tangent to adjacent polygon edges). Let the number of circles with double tangencies be $D$. If $E$ and $F$ are the number of edges and faces of the graph, and $\tilde{E}$ and $\tilde{F}$ are these quantities when the doubled edges are merged into single edges, then $E=\tilde{E}+D$ and $F=\tilde{F}+D$. Since our graph has $n+1$ vertices, and reverse convex programming tells us there is an optimum with $E=3n$ tangencies, Euler's theorem gives $n+1-3n+F=2$, or $F=2n+1$. We therefore have the following formulas for the "reduced graph" after merging doubled edges: $\tilde{E}=3n-D$, $\tilde{F}=2n+1-D$. The reduced graph is simple and planar and satisfies $2\tilde{E}\ge 3\tilde{F}$ where equality implies that the graph is triangulated. Using our formulas this inequality becomes $D\ge 3$.
The result of this analysis is that optimum configurations in the $M$-gon have at least 3 circles with double tangency, and that the reduced graph is triangulated when this minimum holds. The number 3 is interesting. I believe it corresponds to the fact that the conformal transformations are fixed by specifying 3 points on the boundary of the region (the $M$-gon) where the circles are mapped. Sacrificing the symmetry of the fixed circle paid off because it allowed the optimization problem to have discrete solutions (whose existence follow from reverse convex programming).
There are two gaps in the proof. How do we take results for the $M$-gon and by some limiting process prove a theorem about the circle? Second, how do we prove $D=3$? Optimal configurations with $D>3$ become more unlikely as $M$ becomes large because in that case more than the minimum number of active constraints arise from double tangencies. After all, the pair of constraints at a double tangency become degenerate at $M=\infty$.
I believe the conjecture is true for the class of objective functions $r_1^p+\cdots + r_n^p$ where $1\le p < 2$. The case $p\ge 2$ is uninteresting because the optima degenerate into a single circle that completely fills the fixed circle, the rest having zero radius.
