On asymptotic packing of geometric graphs

DOI10.1016/J.DAM.2022.07.030MaRDI QIDQ2081476zbMATH OpenOpenAlexWikidataFDO

Authors Daniel W. Cranston, Jiaxi Nie, Alexandra Wesolek, J. Verstraëte

Publication date 13 October 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2111.03933

zbMATH Keywords

convex geometric graphgeometric graphgraph packing

Mathematics Subject Classification ID

Triple systems (05B07) Combinatorial aspects of packing and covering (05B40) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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$.

Recommendations

• Planar packing of cycles and unicyclic graphs
• Packing plane spanning trees and paths in complete geometric graphs
• Two theorems on packings of graphs
• Packing trees into planar graphs
• scientific article; zbMATH DE number 1342089

Cites work

• A lower bound for the optimal crossing-free Hamiltonian cycle problem
• A proof of Ringel's conjecture
• Combinatorial and computational aspects of graph packing and graph decomposition
• scientific article; zbMATH DE number 3503285 (Why is no real title available?)
• On a packing and covering problem
• Packing plane spanning trees and paths in complete geometric graphs
• Packing plane spanning trees into a point set
• Partitions of complete geometric graphs into plane trees
• The book thickness of a graph

Cited in

(2)

• Asymptotics of weighted best-packing on rectifiable sets
• On asymptotic packing of convex geometric and ordered graphs

This page was built for publication: On asymptotic packing of geometric graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2081476)