New bijective links on planar maps via orientations

DOI10.1016/J.EJC.2009.02.008zbMATH Open1188.05054arXiv0810.2607OpenAlexW2130519984WikidataQ114184875 ScholiaQ114184875MaRDI QIDQ1041192FDOQ1041192

Authors: Éric Fusy 

Publication date: 1 December 2009

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

Abstract: This article presents new bijections on planar maps. At first a bijection is established between bipolar orientations on planar maps and specific "transversal structures" on triangulations of the 4-gon with no separating 3-cycle, which are called irreducible triangulations. This bijection specializes to a bijection between rooted non-separable maps and rooted irreducible triangulations. This yields in turn a bijection between rooted loopless maps and rooted triangulations, based on the observation that loopless maps and triangulations are decomposed in a similar way into components that are respectively non-separable maps and irreducible triangulations. This gives another bijective proof (after Wormald's construction published in 1980) of the fact that rooted loopless maps with $n$ edges are equinumerous to rooted triangulations with $n$ inner vertices.

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

Recommendations

• New bijective links on planar maps
• A unified bijective method for maps: application to two classes with boundaries
• Bijections for planar maps with boundaries
• A generic method for bijections between blossoming trees and planar maps
• A bijective census of nonseparable planar maps

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Cites Work

• A Census of Planar Maps
• Graphs on surfaces
• Title not available (Why is that?)
• Title not available (Why is that?)
• A bijective census of nonseparable planar maps
• Random maps, coalescing saddles, singularity analysis, and Airy phenomena
• On Finding the Rectangular Duals of Planar Triangular Graphs
• Optimal coding and sampling of triangulations
• Transversal structures on triangulations: A combinatorial study and straight-line drawings
• Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems
• A Census of Planar Triangulations
• On the Enumeration of Rooted Non-Separable Planar Maps
• Bijections for Baxter families and related objects
• Four classes of pattern-avoiding permutations under one roof: Generating trees with two labels
• Dissections, orientations, and trees with applications to optimal mesh encoding and random sampling
• Bipolar orientations revisited
• Bijective counting of plane bipolar orientations and Schnyder woods
• Dichromatic polynomials and Potts models summed over rooted maps
• On some complexity properties of N-free posets and posets with bounded decomposition diameter
• Planarity and edge poset dimension
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (13)

• On the enumeration of plane bipolar posets and transversal structures
• Bijective counting of plane bipolar orientations
• Planar triangulations, bridgeless planar maps and Tamari intervals
• On irreducible maps and slices
• Bijections for planar maps with boundaries
• Orientations and bijections for toroidal maps with prescribed face-degrees and essential girth
• New bijective links on planar maps
• Random cubic planar maps
• A bijection for triangulations of a polygon with interior points and multiple edges
• A unified bijective method for maps: application to two classes with boundaries
• The scaling limit of random cubic planar graphs
• The combinatorics of a tree-like functional equation for connected chord diagrams
• A generic method for bijections between blossoming trees and planar maps

This page was built for publication: New bijective links on planar maps via orientations

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