pith. sign in

arxiv: 2606.29743 · v1 · pith:JT3D6ELMnew · submitted 2026-06-29 · 💻 cs.DM · math.CO

3-packings in Triangulations: Algorithms, bounds, and Complexity

Prosenjit Bose , Anil Maheshwari , Bobby Miraftab , Yota Otachi This is my paper

Pith reviewed 2026-06-30 04:01 UTC · model grok-4.3

classification 💻 cs.DM math.CO
keywords plane triangulationspackingsP3induced packingstriangle factorsgraph algorithmsmaximal planar
0
0 comments X

The pith

Every triangulation on n vertices has a P3-packing of size at least floor(n/5), and this bound is asymptotically tight.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves lower bounds on the maximum number of vertex-disjoint copies of three small graphs that can be packed into a plane triangulation. For paths on three vertices, every triangulation admits at least floor(n/5) such copies, and examples show that this is the best possible in the limit. For induced copies of an edge plus an isolated vertex, the bound improves to floor(n/3) minus 2, and an efficient algorithm constructs the packing. Additional results bound triangle packings by degree and characterize when a triangulation has a triangle factor.

Core claim

For P3-packings in triangulations, λ_P3(G) is at least floor(n/5) for any triangulation G on n vertices, and the bound is asymptotically tight. For induced packings of P2 ∪ P1 in plane triangulations T, λ_{P2∪P1}(T) is at least floor(n/3)-2 and such packings can be computed in polynomial time. Lower bounds for K3-packings are given in terms of maximum degree and degree sequence, and a face-path characterization is provided for triangle factors in 4-connected plane triangulations.

What carries the argument

The function λ_H(G) measuring the maximum number of vertex-disjoint copies of H in G, with the induced requirement for H = P2 ∪ P1.

If this is right

  • A polynomial-time algorithm exists to find the induced P2∪P1 packing.
  • Triangle packings can be bounded using the maximum degree.
  • Triangle factors in 4-connected triangulations are characterized by a hamiltonian cycle and weak duals of maximal outerplanar graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The asymptotic tightness implies there exist infinite families of triangulations achieving roughly n/5.
  • Similar packing results might hold for other classes of planar graphs.
  • The polynomial algorithm suggests practical applications in graph decomposition problems.

Load-bearing premise

The graphs under consideration are exactly the plane triangulations, meaning maximal planar graphs, and the definition of packing for P2 ∪ P1 requires induced copies.

What would settle it

Finding a triangulation on a large number of vertices where the largest P3-packing has size less than n/5 would falsify the main lower bound.

Figures

Figures reproduced from arXiv: 2606.29743 by Anil Maheshwari, Bobby Miraftab, Prosenjit Bose, Yota Otachi.

Figure 1
Figure 1. Figure 1: Possible cases for Tv We now combine the two previous lemmas to obtain the desired lower bound for triangulations. Theorem 3. Let G be a triangulation of order n. Then λ(G) ≥ j n 5 k . 4 [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A triangulation H = K4 in the left and the triangulation G4 in the right obtained by adding two vertices in each face. The red paths are the four disjoint copies of P3, namely xfv vyfv for v ∈ V (H). Open Problem 1. Determine the computational complexity of maximum P3-packing in plane triangulations. More precisely, given a plane triangulation G and an integer k, decide whether λ(G) ≥ k. Is this problem so… view at source ↗
Figure 3
Figure 3. Figure 3: The plane graph G in gray and the graph H in black. The advantage of this auxiliary graph is that it turns the packing problem into an independent set problem. Indeed, a set of facial triangles is pairwise vertex-disjoint in G precisely when the corresponding vertices are independent in H. Thus any lower bound on α(H) immediately gives a lower bound on ν3(G). In order to apply such a bound effectively, we … view at source ↗
Figure 4
Figure 4. Figure 4: A small Eulerian triangulation with ∆(G) = 6 and (∆1,∆2,∆3) = (6,4,4), so ∆1 + ∆2 +∆3 = 14 < 18 = 3∆(G). 3.1 Algorithmic form of the packing bounds The lower bounds above are constructive. Let G be a simple plane triangulation on n > 3 vertices, and let H be the auxiliary graph whose vertices are the facial triangles of G, with two vertices adjacent whenever the corresponding faces share a vertex. Every in… view at source ↗
Figure 5
Figure 5. Figure 5: The face gadget used to triangulate a non-triangular face [PITH_FULL_IMAGE:figures/full_fig_p017_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Figure (a) shows the full triangulation G with hamiltonian cycle C = v1v2 ···v6v1. Figures (b) and (c) show the two maximal outerplanar graphs G+ and G− determined by C, together with their weak duals T + and T − . The red triangles/nodes indicate the selected faces t + 2 and t − 2 , while the green paths indicate P + 6 and P − 6 . Corollary 25. Let G be a 4-connected plane triangulation. Let I : V (G) → {… view at source ↗
Figure 7
Figure 7. Figure 7: Illustration of the construction in the proof of [PITH_FULL_IMAGE:figures/full_fig_p022_7.png] view at source ↗
read the original 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 $\lambda_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 $\lambda_{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 $\lambda_{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 $\lambda_{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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript studies H-packings in plane triangulations for the three-vertex graphs H in {P3, K3, P2 ∪ P1}. It proves that every triangulation G on n vertices satisfies λ_P3(G) ≥ ⌊n/5⌋ and that this lower bound is asymptotically tight. Lower bounds are given for λ_K3(G) in terms of maximum degree and the degree sequence. A face-path characterization of triangle factors is provided for 4-connected plane triangulations using a Hamiltonian cycle and the weak duals of the two associated maximal outerplanar graphs. For induced packings by P2 ∪ P1, it proves that every plane triangulation T on n vertices satisfies λ_{P2∪P1}(T) ≥ ⌊n/3⌋-2 and that such a packing can be found in polynomial time.

Significance. If the proofs and algorithm are correct, the results would constitute a useful contribution to packing problems in maximal planar graphs. The asymptotic tightness of the P3 bound and the polynomial-time algorithm for the induced P2 ∪ P1 packing are notable strengths, as they combine a sharp theoretical guarantee with an efficient constructive method. The degree-based bounds on triangle packings and the structural characterization for triangle factors add further value for understanding the extremal and algorithmic properties of triangulations.

minor comments (2)
  1. [Abstract] Abstract: the definition of λ_H(G) and the induced-copy convention for H = P2 ∪ P1 are stated, but the main text should cross-reference these definitions explicitly when presenting the algorithm and the lower-bound proof to avoid any ambiguity for readers.
  2. [Abstract] The title includes 'Complexity' yet the abstract only reports a polynomial-time algorithm; if the manuscript contains additional complexity results (e.g., NP-hardness for related problems), they should be summarized in the abstract for completeness.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. The report lists no specific major comments under the MAJOR COMMENTS section.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper presents direct mathematical proofs establishing lower bounds such as λ_P3(G) ≥ ⌊n/5⌋ for any triangulation G on n vertices (asymptotically tight) and λ_{P2∪P1}(T) ≥ ⌊n/3⌋-2 for plane triangulations T, along with a polynomial-time algorithm. These results rely on graph-theoretic arguments, face-path characterizations, and constructive methods applied to the stated definitions of H-packings in maximal planar graphs. No equations, parameters, or claims reduce by construction to fitted inputs, self-definitions, or load-bearing self-citations; the derivation chain is self-contained with independent content.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, invented entities, or non-standard axioms are introduced or fitted in the abstract; all claims rest on the standard definitions of plane triangulations and H-packings.

pith-pipeline@v0.9.1-grok · 5798 in / 1194 out tokens · 53201 ms · 2026-06-30T04:01:51.054661+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

23 extracted references · 13 canonical work pages

  1. [1]

    Noga Alon and Raphael Yuster.H-factors in dense graphs.J. Combin. Theory Ser. B, 66(2):269–282, 1996.doi:10.1006/jctb.1996.0020. 23

    work page doi:10.1006/jctb.1996.0020 1996

  2. [2]

    Brenda S. Baker. Approximation algorithms for NP-complete problems on planar graphs.Journal of the ACM, 41(1):153–180, 1994

    1994

  3. [3]

    Barnette

    David W. Barnette. Trees in polyhedral graphs.Canadian Journal of Mathematics, 18:731–736, 1966.doi:10.4153/CJM-1966-073-4

    work page doi:10.4153/cjm-1966-073-4 1966

  4. [4]

    Trees and co-trees with constant maximum degree in planar 3- connected graphs.ArXiv, abs/1312.4101, 2013.1312.4101

    Therese Biedl. Trees and co-trees with constant maximum degree in planar 3- connected graphs.ArXiv, abs/1312.4101, 2013.1312.4101

    Pith/arXiv arXiv 2013

  5. [5]

    Packing triangles in bounded degree graphs.In- form

    Alberto Caprara and Romeo Rizzi. Packing triangles in bounded degree graphs.In- form. Process. Lett., 84(4):175–180, 2002.doi:10.1016/S0020-0190(02)00274-0

    work page doi:10.1016/s0020-0190(02)00274-0 2002

  6. [6]

    New results on the independence number

    Yair Caro. New results on the independence number. Technical report, Tel-Aviv University, 1979

    1979

  7. [7]

    Corradi and A

    K. Corradi and A. Hajnal. On the maximal number of independent circuits in a graph. Acta Math. Acad. Sci. Hungar., 14:423–439, 1963.doi:10.1007/BF01895727

    work page doi:10.1007/bf01895727 1963

  8. [8]

    Wayne Goddard and Michael A. Henning. Thoroughly distributed colorings.ArXiv, 2016.1609.09684

    arXiv 2016

  9. [9]

    Pandu Rangan, Maw-Shang Chang, Gerard J

    Venkatesan Guruswami, C. Pandu Rangan, Maw-Shang Chang, Gerard J. Chang, and C. K. Wong. The vertex-disjoint triangles problem. In Juraj Hromkovičand Ondrej Sýkora, editors,Graph-Theoretic Concepts in Computer Science, volume 1517 ofLecture Notes in Computer Science, pages 26–37. Springer, Berlin, Heidelberg, 1998.doi: 10.1007/10692760_3

    work page doi:10.1007/10692760_3 1998

  10. [10]

    Hell and D

    P . Hell and D. G. Kirkpatrick. On generalized matching problems.Inform. Process. Lett., 12(1):33–35, 1981.doi:10.1016/0020-0190(81)90073-9

    work page doi:10.1016/0020-0190(81)90073-9 1981

  11. [11]

    On packing 3- vertex paths in a graph.J

    Atsushi Kaneko, Alexander Kelmans, and Tsuyoshi Nishimura. On packing 3- vertex paths in a graph.J. Graph Theory, 36(4):175–197, 2001.doi:10.1002/ 1097-0118(200104)36:4<175::AID-JGT1005>3.0.CO;2-T

    2001

  12. [12]

    Packing 3-vertex paths in claw-free graphs and related topics

    Alexander Kelmans. Packing 3-vertex paths in claw-free graphs and related topics. Discrete Appl. Math., 159(2-3):112–127, 2011.doi:10.1016/j.dam.2010.05.001

    work page doi:10.1016/j.dam.2010.05.001 2011

  13. [13]

    D. G. Kirkpatrick and P . Hell. On the complexity of general graph factor problems. SIAM J. Comput., 12(3):601–609, 1983.doi:10.1137/0212040

    work page doi:10.1137/0212040 1983

  14. [14]

    The minimum degree threshold for perfect graph packings.Combinatorica, 29(1):65–107, 2009.doi:10.1007/s00493-009-2254-3

    Daniela Kühn and Deryk Osthus. The minimum degree threshold for perfect graph packings.Combinatorica, 29(1):65–107, 2009.doi:10.1007/s00493-009-2254-3

    work page doi:10.1007/s00493-009-2254-3 2009

  15. [15]

    Vazirani

    Silvio Micali and Vijay V. Vazirani. AnO( √ |V| |E|) algorithm for finding maximum matching in general graphs. In21st Annual Symposium on Foundations of Computer Science, pages 17–27. 1980

    1980

  16. [16]

    Lower bounds on the cardinality of the maximum matchings of planar graphs.Discrete Mathematics, 28(3):255–267, 1979.doi:10

    Takao Nishizeki and Ilker Baybars. Lower bounds on the cardinality of the maximum matchings of planar graphs.Discrete Mathematics, 28(3):255–267, 1979.doi:10. 1016/0012-365X(79)90133-X. 24

    1979

  17. [17]

    Daniel P . Sanders. On hamilton cycles in certain planar graphs.Journal of Graph Theory, 21(1):43–50, 1996.doi:10.1002/(SICI)1097-0118(199601)21:1<43:: AID-JGT6>3.0.CO;2-M

    work page doi:10.1002/(sici)1097-0118(199601)21:1 1996

  18. [18]

    The complexity of pinning sim- ple multiloops.arXiv preprint arXiv:2602.07344, 2026

    Eric Seo, Christopher-Lloyd Simon, and Ben Stucky. The complexity of pinning sim- ple multiloops.arXiv preprint arXiv:2602.07344, 2026

    arXiv 2026

  19. [19]

    An improved kernel for planar vertex-disjoint triangle packing.Theoret

    Zimo Sheng and Mingyu Xiao. An improved kernel for planar vertex-disjoint triangle packing.Theoret. Comput. Sci., 922:122–130, 2022.doi:10.1016/j.tcs.2022.04. 017

    work page doi:10.1016/j.tcs.2022.04 2022

  20. [20]

    W. T. Tutte. A theorem on planar graphs.Trans. Amer. Math. Soc., 82:99–116, 1956. doi:10.2307/1992980

    work page doi:10.2307/1992980 1956

  21. [21]

    NP-complete problems on a 3-connected cubic planar graph and their applications

    Ryuhei Uehara. NP-complete problems on a 3-connected cubic planar graph and their applications. Technical Report TWCU-M-0004, Tokyo Woman’s Christian Uni- versity, 1996

    1996

  22. [22]

    V. K. Wei. A lower bound on the stability number of a simple graph. Technical Report 81-11217-9, Bell Laboratories, Murray Hill, NJ, 1981

    1981

  23. [23]

    Non-separable and planar graphs.Trans

    Hassler Whitney. Non-separable and planar graphs.Trans. Amer. Math. Soc., 34(2):339–362, 1932.doi:10.2307/1989545. 25

    work page doi:10.2307/1989545 1932