Back to Search
Start Over
On Asymptotic Packing of Geometric Graphs
- Source :
- Discrete Applied Math. Volume 322, 15 December 2022, Pages 142-152
- Publication Year :
- 2021
-
Abstract
- A set of geometric graphs is {\em geometric-packable} if it can be asymptotically packed into every sequence of drawings of the complete graph $K_n$. 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 {\em 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 $K_n$.
- Subjects :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Journal :
- Discrete Applied Math. Volume 322, 15 December 2022, Pages 142-152
- Publication Type :
- Report
- Accession number :
- edsarx.2111.03933
- Document Type :
- Working Paper