Back to Search
Start Over
On asymptotic packing of geometric graphs.
- Source :
-
Discrete Applied Mathematics . Dec2022, Vol. 322, p142-152. 11p. - Publication Year :
- 2022
-
Abstract
- A set of geometric graphs is 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 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 322
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 159565431
- Full Text :
- https://doi.org/10.1016/j.dam.2022.07.030