Answers are grounded in this paper and cite their sources.
Combinatorial analysis reveals a bijection to oriented binary trees in rooted plane graphs, facilitating exact counting and efficient random sampling.
This paper is concerned with the counting and random sampling of plane graphs (simple planar graphs embedded in the plane). Our main result is a bijection between the class of plane graphs with triangular outer face, and a class of oriented binary trees. The number of edges and vertices of the plane graph can be tracked through the bijection. Consequently, we obtain counting formulas and an efficient random sampling algorithm for rooted plane graphs (with arbitrary outer face) according to the number of edges and vertices. We also obtain a bijective link, via a bijection of Bona, between rooted plane graphs and 1342-avoiding permutations.
No takes yet. Share an insight, caveat, or question.
Bernardi et al. (2013) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: