3-packings in Triangulations: Algorithms, bounds, and Complexity
2026-06-29 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study how to fit certain small graphs, called packings, into plane triangulations (graphs drawn on a plane where every face is a triangle). They focus on three small graphs: a 3-vertex path, a triangle, and a graph with one edge plus an isolated vertex. They prove minimum numbers of these packings that can always be found in such triangulations and provide ways to find them efficiently. They also explore special structures related to triangle packings in highly connected cases.
plane triangulationgraph packingP3 (3-vertex path)K3 (triangle graph)induced subgraphmaximum degreeouterplanar graphhamiltonian cycleweak dual graph
Authors
Prosenjit Bose, Anil Maheshwari, Bobby Miraftab, Yota Otachi
Abstract
We study $H$-packings in plane triangulations for the three-vertex graphs $H\in\{P_3,K_3,P_2\cup P_1\}$. For a graph $H$, let $λ_H(G)$ denote the maximum size of an $H$-packing in $G$, with the convention that for $H=P_2\cup P_1$ the copies are required to be induced. For $P_3$-packings, we prove that every triangulation $G$ on $n$ vertices satisfies $λ_{P_3}(G)\ge \left\lfloor \frac n5\right\rfloor$, and show that this lower bound is asymptotically tight. We also study triangle packings in triangulations and provide lower bounds for $λ_{K_3}(G)$ in terms of the maximum degree and the degree sequence. We give a face-path characterization of triangle factors in $4$-connected plane triangulations using a hamiltonian cycle and the weak duals of the two associated maximal outerplanar graphs. Finally, for induced packings by $P_2\cup P_1$, we prove that every plane triangulation $T$ on $n$ vertices satisfies $λ_{P_2\cup P_1}(T)\ge \left\lfloor \frac n3\right\rfloor-2$, and show that such a packing can be found in polynomial time.