On asymptotic packing of geometric graphs

A set of geometric graphs is geometric-packable if it can be asymptotically packed into every sequence of drawings of the complete graph Kn. For example, the set of geometric triangles is geometric-packable due to the existence of Steiner Triple Systems. When G is the 4-cycle (or 4-cycle with a chord), we show that the set of plane drawings of G is geometric-packable. In contrast, the analogous statement is false when G is nearly any other planar Hamiltonian graph (with at most 3 possible exceptions). A convex geometric graph is convex-packable if it can be asymptotically packed into the convex drawings of the complete graphs. For each planar Hamiltonian graph G, we determine whether or not a plane G is convex-packable. Many of our proofs explicitly construct these packings; in these cases, the packings exhibit a symmetry that mirrors the vertex transitivity of Kn. (c) 2022 Elsevier B.V. All rights reserved.

Automated summary

This article investigates whether a set of geometric graphs can be packed into complete graphs and convex drawings. It is shown that certain geometric shapes such as triangles and 4-cycles can be packed, while most other planar Hamiltonian graphs cannot.