Enumeration of chordal planar graphs and maps

Abstract

We determine the number of labelled chordal planar graphs with n vertices, which is asymptotically g⋅n−5/2γnn! for a constant g>0 and γ≈11.89235. We also determine the number of rooted simple chordal planar maps with n edges, which is asymptotically s⋅n−3/2δn, where s>0, δ=1/σ≈6.40375, and σ is an algebraic number of degree 12. The proofs are based on combinatorial decompositions and singularity analysis. Chordal planar graphs (or maps) are a natural example of a subcritical class of graphs in which the class of 3-connected graphs is relatively rich. The 3-connected members are precisely chordal triangulations, those obtained starting from K4 by repeatedly adding vertices adjacent to an existing triangular face. © 2022 The Author(s)