On contact graphs of totally separable packings in low dimensions

Abstract

The contact graph of a packing of translates of a convex body in Euclidean d-space Ed is the simple graph whose vertices are the members of the packing, and whose two vertices are connected by an edge if the two members touch each other. A packing of translates of a convex body is called totally separable, if any two members can be separated by a hyperplane in Ed disjoint from the interior of every packing element. We give upper bounds on the maximum degree (called separable Hadwiger number) and the maximum number of edges (called separable contact number) of the contact graph of a totally separable packing of n translates of an arbitrary smooth convex body in Ed. In the proofs, linear algebraic and convexity methods are combined with volumetric and packing density estimates based on the underlying isoperimetric (resp., reverse isoperimetric) inequality.

MSC

primary

05C10
52C15

secondary

05B40
46B20

Keywords

Convex body
Totally separable packing
Hadwiger number
Separable Hadwiger number
Contact graph
Contact number
Separable contact number