pith. sign in

arxiv: 2606.17992 · v1 · pith:KZXLJIGHnew · submitted 2026-06-16 · 🧮 math.CO · math.PR

Asymptotic enumeration of unlabelled cubic planar graphs

Benedikt Stufler This is my paper

Pith reviewed 2026-06-26 23:57 UTC · model grok-4.3

classification 🧮 math.CO math.PR
keywords asymptotic enumerationcubic planar graphsunlabelled graphsgenerating serieslarge deviation theoremsplanar maps
0
0 comments X

The pith

The precise asymptotic number of unlabelled cubic planar graphs on n vertices is obtained by blending generating series, computational bounds, and local large deviation theorems.

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

The paper establishes the exact asymptotic growth for the count of distinct cubic planar graphs with n vertices, where two graphs are identified if one can be obtained from the other by relabelling. It does so by combining analytic generating-function techniques with numerical bounds and probabilistic results on local large deviations. A sympathetic reader would care because this supplies a sharp formula rather than bounds or approximations, which in turn supports the study of typical features in a random graph drawn from this class. The work closes a gap between labelled and unlabelled enumeration for this restricted family of planar graphs.

Core claim

We determine the precise asymptotic number of unlabelled cubic planar graphs with n vertices. Our approach blends generating series methods with computational bounds and probabilistic local large deviation theorems.

What carries the argument

The blended use of generating series methods, computational bounds, and probabilistic local large deviation theorems to extract the exact asymptotic formula.

If this is right

  • The leading exponential growth rate and the precise polynomial correction term become available for direct numerical use.
  • Probabilistic statements about properties of a uniformly random unlabelled cubic planar graph on n vertices can be derived from the asymptotic.
  • The same combination of tools applies directly to the enumeration of other unlabelled planar graph families that admit similar generating-function descriptions.

Where Pith is reading between the lines

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

  • The technique may resolve asymptotics for unlabelled planar graphs with additional constraints such as prescribed face degrees or higher connectivity.
  • The resulting formula supplies a benchmark against which sampling algorithms for planar graphs can be tested for bias.
  • Limit laws for global parameters such as diameter or number of components in the random model become accessible once the enumeration is settled.

Load-bearing premise

The generating series methods, computational bounds, and probabilistic local large deviation theorems can be blended to yield the precise asymptotic without unaccounted errors or approximations.

What would settle it

An exact enumeration of the graphs for a concrete large n whose ratio to the predicted asymptotic expression fails to approach 1.

Figures

Figures reproduced from arXiv: 2606.17992 by Benedikt Stufler.

Figure 1
Figure 1. Figure 1: An achiral graph on the left and a chiral graph on the right. Likewise, an unlabelled 3-connected planar graph with an oriented root edge may correspond to one or two rooted planar maps. We call it accordingly rooted achiral or rooted chiral. The number of embeddings need not be identical to the number of embeddings of the underlying unrooted graph. See [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: On the left: a rooted graph that is rooted achiral and also achiral as an unrooted graph. On the right: a rooted graph that is rooted chiral but achiral as an unrooted graph. For vertex-labelled planar maps the neighbours of any vertex are cyclically or￾dered. Orientation-preserving homeomorphisms of the sphere preserve this ordering, whereas orientation-reversing homeomorphisms reverse it. Hence any verte… view at source ↗
Figure 3
Figure 3. Figure 3: Two vertex-labelled planar maps that are not related through an orientation-preserving homeomorphism, although the corresponding un￾labelled planar map is achiral. 2.3. Automorphisms of 3-connected planar graphs. — It was shown by [54] that any 3-connected planar graph with m edges has at most 4m automorphisms. That [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Decomposition of loop networks. 3.2.2. Isthmus networks. — An isthmus network N corresponds to an ordered pair of loop networks, each having an additional vertex. See [PITH_FULL_IMAGE:figures/full_fig_p013_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Decomposition of isthmus networks. 3.2.3. Series networks. — Let N denote a series network with poles s and t. Then N − e contains one or more bridges that separate the poles. Let uv denote the bridge that is closest to s, directed from u to v such that u is closer to s than v. Then, as illustrated in [PITH_FULL_IMAGE:figures/full_fig_p013_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Decomposition of series networks. 3.2.4. Parallel networks. — We distinguish two types of parallel networks, corre￾sponding to species Ps and Pd, depending on whether the root edge is a simple edge or a double edge. If the root edge of a parallel network N is a double edge, then its poles s and t are adjacent to (possibly identical) vertices u and v, which form the poles of a smaller non-isthmus network. S… view at source ↗
Figure 7
Figure 7. Figure 7: Decomposition of the two types of parallel networks. 3.2.5. Polyhedral networks. — A polyhedral network N is obtained from a 3- connected cubic planar graph M with a directed root edge by inserting components D(1), D(2), . . . at its non-root edges as illustrated in [PITH_FULL_IMAGE:figures/full_fig_p015_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Decomposition of polyhedral networks. Recall that qn denotes the number of 3-connected rooted cubic planar maps with 2n vertices and hence 3n edges. Proposition 3.2. — There exist multivariate power series R1(s1, s2, a1, a2, b1) and R2(s1, s2, a1, a2, b1) with nonnegative coefficients and a constant 0 < c < 1 such that for all n ≥ 2 and i = 1, 2 [x 2n y 3n−1 ]Ri(x, x2 , y, y2 , y) = O(c n )qn, [PITH_FULL_… view at source ↗
read the original abstract

We determine the precise asymptotic number of unlabelled cubic planar graphs with $n$ vertices. Our approach blends generating series methods with computational bounds and probabilistic local large deviation theorems.

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 / 1 minor

Summary. The paper determines the precise asymptotic number of unlabelled cubic planar graphs on n vertices. The approach combines generating-function singularity analysis, computational enumeration bounds, and probabilistic local large-deviation estimates.

Significance. If the central derivation holds, the result supplies an exact leading asymptotic term for an important subclass of planar graphs, extending classical enumeration results. The explicit blend of analytic, computational, and probabilistic tools is a methodological strength when the error terms are fully controlled.

minor comments (1)
  1. The abstract describes the method at a high level; the manuscript should include explicit statements of the singularity type, the radius of convergence, and the precise form of the asymptotic (e.g., c · ρ^{-n} n^{-5/2} or similar) with all constants computed or bounded.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their report and for acknowledging the potential significance of our asymptotic enumeration result for unlabelled cubic planar graphs, as well as the methodological combination of generating-function techniques, computational bounds, and probabilistic estimates. We note the 'uncertain' recommendation but observe that the report contains no specific major comments or questions regarding the central derivation, error control, or any other aspect of the manuscript.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's approach combines generating series methods, computational bounds, and probabilistic local large deviation theorems to derive the asymptotic count. These are standard, externally established tools (singularity analysis, enumeration algorithms, and large-deviation theory) whose validity does not depend on the target result. No load-bearing self-citations, self-definitional steps, or fitted inputs renamed as predictions are identifiable from the abstract or description. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No details available from the abstract to identify any free parameters, axioms, or invented entities.

pith-pipeline@v0.9.1-grok · 5527 in / 1051 out tokens · 42512 ms · 2026-06-26T23:57:40.395341+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

59 extracted references

  1. [1]

    Armend´ ariz and M

    I. Armend´ ariz and M. Loulakis. Conditional distribution of heavy tailed random vari- ables on large deviations of their sum.Stochastic Process. Appl., 121(5):1138–1147, 2011

    2011

  2. [2]

    E. A. Bender and E. R. Canfield. The asymptotic number of rooted maps on a surface. J. Comb. Theory, Ser. A, 43:244–257, 1986

    1986

  3. [3]

    E. A. Bender, Z. Gao, and N. C. Wormald. The number of labeled 2-connected planar graphs.Electron. J. Combin., 9(1):Research Paper 43, 13, 2002

    2002

  4. [4]

    E. A. Bender, Z.-C. Gao, and L. B. Richmond. Submaps of maps. I: General 0-1 laws. J. Comb. Theory, Ser. B, 55(1):104–117, 1992. 88

    1992

  5. [5]

    E. A. Bender and N. C. Wormald. Almost all convex polyhedra are asymmetric.Can. J. Math., 37:854–871, 1985

    1985

  6. [6]

    E. A. Bender and N. C. Wormald. The asymptotic number of rooted nonseparable maps on a surface.J. Comb. Theory, Ser. A, 49(2):370–380, 1988

    1988

  7. [7]

    Bergeron, G

    F. Bergeron, G. Labelle, and P. Leroux.Combinatorial species and tree-like structures, volume 67 ofEncyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1998. Translated from the 1994 French original by Margaret Readdy, With a foreword by Gian-Carlo Rota

    1998

  8. [8]

    Bodirsky, C

    M. Bodirsky, C. Gr ¨opl, and M. Kang. Generating unlabeled connected cubic planar graphs uniformly at random.Random Struct. Algorithms, 32(2):157–180, 2008

    2008

  9. [9]

    Bodirsky, M

    M. Bodirsky, M. Kang, M. L ¨offler, and C. McDiarmid. Random cubic planar graphs. Random Struct. Algorithms, 30(1-2):78–94, 2007

    2007

  10. [10]

    Brinkmann

    G. Brinkmann. Fast generation of planar graphs.MATCH Commun. Math. Comput. Chem., 58(2):323–357, 2007

    2007

  11. [11]

    Brinkmann, S

    G. Brinkmann, S. Greenberg, C. Greenhill, B. D. McKay, R. Thomas, and P. Wollan. Generation of simple quadrangulations of the sphere.Discrete Math., 305(1-3):33–54, 2005

    2005

  12. [12]

    Brinkmann and B

    G. Brinkmann and B. D. McKay. Construction of planar triangulations with minimum degree 5.Discrete Math., 301(2-3):147–163, 2005

    2005

  13. [13]

    W. G. Brown. Enumeration of triangulations of the disk.Proc. London Math. Soc. (3), 14:746–768, 1964

    1964

  14. [14]

    Chover, P

    J. Chover, P. Ney, and S. Wainger. Functions of probability measures.J. Analyse Math., 26:255–302, 1973

    1973

  15. [15]

    Denisov, A

    D. Denisov, A. B. Dieker, and V. Shneer. Large deviations for random walks under subexponentiality: the big-jump domain.Ann. Probab., 36(5):1946–1991, 2008

    1946

  16. [16]

    Embrechts

    P. Embrechts. The asymptotic behaviour of series and power series with positive coef- ficients.Med. Konink. Acad. Wetensch. Belgi ¨e, 45(1):41–61, 1983

    1983

  17. [17]

    Embrechts and E

    P. Embrechts and E. Omey. Functions of power series.Yokohama Math. J., 32(1-2):77– 88, 1984

    1984

  18. [18]

    Flajolet and R

    P. Flajolet and R. Sedgewick.Analytic combinatorics. Cambridge University Press, Cambridge, 2009

    2009

  19. [19]

    S. Foss, D. Korshunov, and S. Zachary.An introduction to heavy-tailed and subexpo- nential distributions. Springer Series in Operations Research and Financial Engineering. Springer, New York, second edition, 2013

    2013

  20. [20]

    Gagarin, G

    A. Gagarin, G. Labelle, and P. Leroux. The structure and labelled enumeration ofK 3,3- subdivision-free projective-planar graphs.PU.M.A., Pure Math. Appl., 16(3):267–286, 2005

    2005

  21. [21]

    Gagarin, G

    A. Gagarin, G. Labelle, and P. Leroux. The structure and unlabelled enumeration of toroidal graphs with noK 3,3’s. InFifth Cracow conference on graph theory, USTRON ’06, Ustro´ n, Poland, September 11–15, 2006, pages 69–76. Amsterdam: Elsevier, 2006

    2006

  22. [22]

    Gagarin, G

    A. Gagarin, G. Labelle, and P. Leroux. Counting unlabelled toroidal graphs with no K3,3-subdivisions.Adv. Appl. Math., 39(1):51–75, 2007

    2007

  23. [23]

    Gagarin, G

    A. Gagarin, G. Labelle, and P. Leroux. The structure ofK 3,3-subdivision-free toroidal graphs.Discrete Math., 307(23):2993–3005, 2007

    2007

  24. [24]

    Gagarin, G

    A. Gagarin, G. Labelle, P. Leroux, and T. Walsh. Structure and enumeration of two- connected graphs with prescribed three-connected components.Adv. in Appl. Math., 43(1):46–74, 2009

    2009

  25. [25]

    Gagarin, G

    A. Gagarin, G. Labelle, P. Leroux, and T. Walsh. Structure and enumeration of two-connected graphs with prescribed three-connected components.Adv. Appl. Math., 43(1):46–74, 2009

    2009

  26. [26]

    Gim´ enez and M

    O. Gim´ enez and M. Noy. Asymptotic enumeration and limit laws of planar graphs.J. Amer. Math. Soc., 22(2):309–329, 2009

    2009

  27. [27]

    T. E. Harris.The theory of branching processes, volume 119 ofGrundlehren Math. Wiss. Springer, Cham, 1963. 89

    1963

  28. [28]

    A. Joyal. Une th´ eorie combinatoire des s´ eries formelles.Adv. in Math., 42(1):1–82, 1981

    1981

  29. [29]

    Kang and P

    M. Kang and P. Spr ¨ussel. Symmetries of unlabelled planar triangulations.Electron. J. Comb., 25(1):38, 2018. Id/No p1.34

    2018

  30. [30]

    Krasikov, A

    I. Krasikov, A. Lev, and B. D. Thatte. Upper bounds on the automorphism group of a graph.Discrete Math., 256(1-2):489–493, 2002

    2002

  31. [31]

    V. A. Liskovets. A census of non-isomorphic planar maps. 1981

    1981

  32. [32]

    V. A. Liskovets and T. R. Walsh. Ten steps to counting planar graphs. Combina- torics, graph theory, and computing, Proc. 18th Southeast. Conf., Boca Raton/Fl. 1987, Congr. Numerantium 60, 269-277 (1987)., 1987

    1987

  33. [33]

    V. A. Liskovets and T. R. Walsh. Counting unrooted maps on the plane.Adv. Appl. Math., 36(4):364–387, 2006

    2006

  34. [34]

    B. D. McKay and A. Piperno. Practical graph isomorphism. II.J. Symb. Comput., 60:94–112, 2014

    2014

  35. [35]

    M. Noy. Random planar graphs and beyond.Proc. ICM, 2014

    2014

  36. [36]

    M. Noy, C. Requil´ e, and J. Ru´ e. Further results on random cubic planar graphs.Random Struct. Algorithms, 56(3):892–924, 2020

    2020

  37. [37]

    Rassoul-Agha and T

    F. Rassoul-Agha and T. Sepp ¨al¨ainen.A course on large deviations with an introduction to Gibbs measures, volume 162. American Mathematical Soc., 2015

    2015

  38. [38]

    S. I. Resnick.Extreme values, regular variation, and point processes, volume 4 ofAppl. Probab.Springer-Verlag, New York, NY, 1987

    1987

  39. [39]

    L. B. Richmond, R. W. Robinson, and N. C. Wormald. On Hamilton cycles in 3- connected cubic maps. Cycles in graphs, Workshop Simon Fraser Univ., Burnaby/Can. 1982, Ann. Discrete Math. 27, 141-149 (1985)., 1985

    1982

  40. [40]

    L. B. Richmond and N. C. Wormald. The asymptotic number of convex polyhedra. Trans. Am. Math. Soc., 273:721–735, 1982

    1982

  41. [41]

    L. B. Richmond and N. C. Wormald. Random triangulations of the plane.Eur. J. Comb., 9(1):61–71, 1988

    1988

  42. [42]

    L. B. Richmond and N. C. Wormald. Almost all quadrangular dissections of the disc are asymmetrical.Math. Chron., 19:63–71, 1990

    1990

  43. [43]

    L. B. Richmond and N. C. Wormald. Almost all maps are asymmetric.J. Comb. Theory, Ser. B, 63(1):1–7, 1995

    1995

  44. [44]

    B. A. Rogozin. On the constant in the definition of subexponential distributions.Theory Probab. Appl., 44(2):409–412, 1999

    1999

  45. [45]

    B. Stufler. Unlabelled Gibbs partitions.Comb. Probab. Comput., 29(2):293–309, 2020

    2020

  46. [46]

    Szewczak and M

    Z. Szewczak and M. Weber. Classical and almost sure local limit theorems. arXiv:2208.02700, 2022

    arXiv 2022

  47. [47]

    Tak´ acs

    L. Tak´ acs. A generalization of the ballot problem and its application in the theory of queues.J. Amer. Statist. Assoc., 57:327–337, 1962

    1962

  48. [48]

    W. Tutte. Chapter 37 - the enumerative theory of planar maps. In J. N. Srivastava, editor,A Survey of Combinatorial Theory, pages 437–448. North-Holland, 1973

    1973

  49. [49]

    W. T. Tutte. A census of planar triangulations.Can. J. Math., 14:21–38, 1962

    1962

  50. [50]

    W. T. Tutte. A census of planar maps.Can. J. Math., 15:249–271, 1963

    1963

  51. [51]

    W. T. Tutte. On the enumeration of convex polyhedra.J. Comb. Theory, Ser. B, 28:105–126, 1980

    1980

  52. [52]

    T. R. S. Walsh. Counting unlabelled three-connected and homeomorphically irreducible two- connected graphs.J. Comb. Theory, Ser. B, 32:12–32, 1982

    1982

  53. [53]

    Watanabe

    T. Watanabe. Convolution equivalence and distributions of random sums.Probab. The- ory Relat. Fields, 142(3-4):367–397, 2008

    2008

  54. [54]

    Weinberg

    L. Weinberg. On the maximum order of the automorphism group of a planar triply connected graph.SIAM J. Appl. Math., 14:729–738, 1966

    1966

  55. [55]

    H. Whitney. 2-isomorphic graphs.Am. J. Math., 55:245–254, 1933

    1933

  56. [56]

    Wielandt

    H. Wielandt. Unzerlegbare, nicht negative Matrizen.Math. Z., 52:642–648, 1950

    1950

  57. [57]

    N. C. Wormald. Counting unrooted planar maps.Discrete Math., 36:205–225, 1981. 90

    1981

  58. [58]

    N. C. Wormald. On the number of planar maps.Can. J. Math., 33:1–11, 1981

    1981

  59. [59]

    H. Zhu, Z. Li, and M. Hayashi. Nearly tight universal bounds for the binomial tail probabilities, 2022. Benedikt Stufler, Vienna University of Technology•E-mail :benedikt.stufler at tuwien.ac.at

    2022