Enumeration of chordal planar graphs and maps

February 27, 2022 ยท The Ethereal ยท ๐Ÿ› Discrete Mathematics

๐Ÿ”ฎ THE ETHEREAL: The Ethereal
Pure theory โ€” exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Jordi Castellvรญ, Marc Noy, Clรฉment Requilรฉ arXiv ID 2202.13340 Category math.CO: Combinatorics Cross-listed cs.DS Citations 1 Venue Discrete Mathematics Last Checked 3 months ago
Abstract
We determine the number of labelled chordal planar graphs with $n$ vertices, which is asymptotically $c_1\cdot n^{-5/2} ฮณ^n n!$ for a constant $c_1>0$ and $ฮณ\approx 11.89235$. We also determine the number of rooted simple chordal planar maps with $n$ edges, which is asymptotically $c_2 n^{-3/2} ฮด^n$, where $ฮด= 1/ฯƒ\approx 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 $K_4$ by repeatedly adding vertices adjacent to an existing triangular face.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

๐Ÿ“œ Similar Papers

In the same crypt โ€” Combinatorics

๐Ÿ”ฎ ๐Ÿ”ฎ The Ethereal

Tables of subspace codes

Daniel Heinlein, Michael Kiermaier, ... (+2 more)

math.CO ๐Ÿ› arXiv ๐Ÿ“š 94 cites 10 years ago