We investigate random connected graphs from a block-stable class whose distribution is weighted based on the number of $2$-connected components, or blocks. This includes the class of planar graphs. For this, we develop a notion of a decorated block tree. Following similar ideas to Fleurat and the second author on block-weighted planar maps, we find a phase transition in the singular behaviour of the appropriate generating function and in the typical structure of the block tree. Moreover, for certain block-stable classes (including planar graphs), we obtain precise enumeration results and determine also the typical sizes of the largest blocks in subcritical, critical, and supercritical regimes. It strengthens previously known results on block sizes in uniform random planar graphs.
Alex: Welcome to another episode of ResearchPod.
Sam: Today we're looking at a paper called "Block-weighted random graphs: planar and beyond," by Mihyun Kang, Zéphyr Salvy, and Ronen Wdowinski. It studies random connected graphs from classes like planar graphs—ones you can draw on a flat page without edges crossing.
Alex: So these planar graphs... and they're weighting them based on blocks?
Sam: Yes. Graphs break down into blocks, which are the toughest connected chunks that stay linked even if you remove one edge or point. Think of them like the strong loops in a chain-link fence that don't snap easily. The paper samples random planar graphs but gives extra weight to those with more blocks.
Alex: The core puzzle is why uniform random planar graphs usually have one giant block taking most of the graph, but favoring more blocks turns the whole thing tree-like with tiny blocks?
Sam: Exactly. In the uniform case, one dominant giant block rules, like a huge city in a road network. Add a parameter u that boosts graphs with more blocks, and past a critical point u_C, a phase transition happens: the structure shifts from graph-like with large blocks to tree-like, where blocks are small and connected by a branching tree skeleton.
Alex: They introduce a decorated block tree to analyze this?
Sam: Yes. Imagine dismantling the graph into its strong blocks and the joints connecting them, then rebuilding as a family tree where each family member has a bouquet of those blocks attached. This decorated block tree acts like a branching process, similar to a family tree where each person has kids following a fixed rule. The weighting u decides if the tree stays compact or spreads out, driving the phase shift.
Alex: For planar graphs, this gives sharper info on block sizes?
Sam: Yes. It strengthens prior results on uniform random planar graphs and extends to block-weighted versions. The key is a general phase transition for block-stable classes, where blocks belong to the same graph class. It shows tree-like versus graph-like regimes depending on u relative to u_C.
Alex: This phase transition changes the sizes of those blocks inside the graphs?
Sam: Yes. Below u_C, in the subcritical phase, the biggest block takes a linear chunk of the whole graph—about the same order as the total size n. The next biggest is much smaller, around n to the power of 2/3.
Alex: Linear for the largest, like the uniform case. What shifts at the critical point?
Sam: At u equals u_C, the critical phase, the largest block shrinks to order n^{2/3}, and so do the others—no single block dominates. Above u_C, in the supercritical phase, even the largest is just logarithmic in n, tiny compared to the graph. This comes from how generating functions behave near their breaking points, revealing growth rates.
Alex: Logarithmic is small, like the height of a balanced tree in computer science. The Gibbs partition ties into why one block doesn't hog everything?
Sam: Yes. At each tree joint, a bouquet of blocks forms, and the biggest claims almost all the size there, minus a small random wiggle. In supercritical graphs, since bouquets stay small, no block grows huge. The paper pins this for planar graphs and classes with a square-root singularity in their block generating function.
Alex: Those block sizes mirror the tree degrees closely—giant linear subcritically, n to the 2/3 at critical, logarithmic supercritical?
Sam: Precisely. In each bouquet, the largest block takes nearly the full size assigned to that spot, minus a bounded random amount from a fixed distribution. The paper calls this a Gibbs partition: one piece hogs most of a fixed total, leaving scraps that stay small and steady. Block sizes follow the same scaling as tree degrees.
Alex: Practically, does this let us generate these graphs on demand, from tree-like to dense?
Sam: Yes—the Boltzmann samplers produce graphs under any u, shifting smoothly from giant-block heavy to tiny-block tree-like as u crosses u_C. This advances understanding in classes like planar or bounded-genus graphs, revealing tree versus graph regimes via block weighting.
Alex: Are there limits to where this analysis holds?
Sam: Yes. It requires the block generating function to have a square-root singularity near its limit for the sharp asymptotics. It applies precisely to planar-like classes, but not yet general minor-closed ones without that behavior. Future work targets those, plus higher genus and scaling limits.
Alex: Fair caveats. Overall, a solid unification of counting and typical structure through that decorated tree lens.
Sam: Exactly. The paper establishes phase transitions in the block tree law, counting asymptotics, and block sizes for block-stable classes, with planar as the showcase. That's the meaningful contribution.
Alex: Well put. Thanks for breaking it down, Sam. Thanks for listening to ResearchPod.