A bijection for essentially 3-connected toroidal maps

DOI10.1016/J.EJC.2020.103290MaRDI QIDQ2033922zbMATH OpenOpenAlexFDO

Authors Nicolas Bonichon, Benjamin Lévêque, Éric Fusy

Publication date 18 June 2021

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.04016

zbMATH Keywords

bivariate generating functiontoroidal triangulations

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30)

Abstract: We present a bijection for toroidal maps that are essentially $3$-connected ($3$-connected in the periodic planar representation). Our construction actually proceeds on certain closely related bipartite toroidal maps with all faces of degree $4$ except for a hexagonal root-face. We show that these maps are in bijection with certain well-characterized bipartite unicellular maps. Our bijection, closely related to the recent one by Bonichon and L'ev^eque for essentially 4-connected toroidal triangulations, can be seen as the toroidal counterpart of the one developed in the planar case by Fusy, Poulalhon and Schaeffer, and it extends the one recently proposed by Fusy and L'ev^eque for essentially simple toroidal triangulations. Moreover, we show that rooted essentially $3$-connected toroidal maps can be decomposed into two pieces, a toroidal part that is treated by our bijection, and a planar part that is treated by the above-mentioned planar case bijection. This yields a combinatorial derivation for the bivariate generating function of rooted essentially $3$-connected toroidal maps, counted by vertices and faces.

Recommendations

• Orientations and bijections for toroidal maps with prescribed face-degrees and essential girth
• A bijection for essentially 4-connected toroidal triangulations
• A Bijection for Rooted Maps on Orientable Surfaces
• A bijection for rooted maps on general surfaces
• New bijective links on planar maps

Cites work

• A bijection for covered maps, or a shortcut between Harer-Zagiers and Jacksons formulas
• A bijection for essentially 4-connected toroidal triangulations
• A bijection for rooted maps on general surfaces
• A Bijection for Rooted Maps on Orientable Surfaces
• A bijection for triangulations, quadrangulations, pentagulations, etc.
• A Census of Planar Maps
• A Census of Planar Triangulations
• A generic method for bijections between blossoming trees and planar maps
• Asymptotic enumeration and limit laws for graphs of fixed genus
• Asymptotic enumeration of constellations and related families of maps on orientable surfaces
• Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees
• Bipolar orientations revisited
• Blossoming bijection for higher-genus maps
• Compact Brownian surfaces. I: Brownian disks
• Counting rooted maps on an orientable surface of any genus by a function of the numbers of vertices and faces
• Dissections, orientations, and trees with applications to optimal mesh encoding and random sampling
• Encoding toroidal triangulations
• scientific article; zbMATH DE number 16301 (Why is no real title available?)
• Lattice structures from planar graphs
• On irreducible maps and slices
• Optimal coding and sampling of triangulations
• Orientations and bijections for toroidal maps with prescribed face-degrees and essential girth
• Planar graphs and poset dimension
• Planar maps as labeled mobiles
• Random sampling of large planar maps and convex polyhedra
• Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems
• Schnyder decompositions for regular plane graphs and application to drawing
• Succinct representations of planar maps
• The asymptotic number of rooted maps on a surface. II: Enumeration by vertices and faces
• The Brownian map is the scaling limit of uniform random plane quadrangulations
• The scaling limit of random simple triangulations and random simple quadrangulations
• Toroidal maps: Schnyder woods, orthogonal surfaces and straight-line representations
• Transversal structures on triangulations: A combinatorial study and straight-line drawings
• Uniqueness and universality of the Brownian map

Cited in

(7)

• Type 3 diminimal maps on the torus
• An inductive definition of cubic toroidal maps
• On polynomials counting essentially irreducible maps
• A bijection for essentially 4-connected toroidal triangulations
• Computation of toroidal Schnyder woods made simple and fast: from theory to practice
• Orientations and bijections for toroidal maps with prescribed face-degrees and essential girth
• Bisingular maps on the torus

This page was built for publication: A bijection for essentially 3-connected toroidal maps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2033922)