Konrad Swanepoel

Contact graphs of totally separable packings

A packing of translates of a convex body is called separable if any two
translates can be separated by a hyperplane that does not intersect the
interior of any translate of the packing.  This notion was introduced by
Gábor Fejes Tóth and László Fejes Tóth in 1973, and studied mostly by
considering the density of such packings.  More recently, Károly Bezdek and
others considered the combinatorial properties of the contact graphs of totally
separable packings.  In a contact graph of a packing, the vertices are the
translates, and two vertices are joined when the two translates touch. We
will discuss the maximum degree (Hadwiger number), minimum degree, and
total number of edges (contact number) of these graphs. In particular, we
completely settle the problem of determining the maximum number of edges
of a contact graph of $n$ translates of a convex disc in the plane, for each
convex disc. This is joint work with Márton Naszódi.