A bijection for essentially 4-connected toroidal triangulations

zbMATH Open1409.05107arXiv1707.08191MaRDI QIDQ668063FDOQ668063

Authors: Nicolas Bonichon, Benjamin Lévêque 

Publication date: 5 March 2019

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Transversal structures (also known as regular edge labelings) are combinatorial structures defined over 4-connected plane triangulations with quadrangular outer-face. They have been intensively studied and used for many applications (drawing algorithm, random generation, enumeration ...). In this paper we introduce and study a generalization of these objects for the toroidal case. Contrary to what happens in the plane, the set of toroidal transversal structures of a given toroidal triangulation is partitioned into several distributive lattices. We exhibit a subset of toroidal transversal structures, called balanced, and show that it forms a single distributive lattice. Then, using the minimal element of the lattice, we are able to enumerate bijectively essentially 4-connected toroidal triangulations.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• A bijection for essentially 3-connected toroidal maps
• Graph Drawing
• Transversal structures on triangulations: A combinatorial study and straight-line drawings
• On the structure of Schnyder woods on orientable surfaces
• Encoding toroidal triangulations

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Planar maps as labeled mobiles
• Lattice structures from planar graphs
• A Bijection for Rooted Maps on Orientable Surfaces
• 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 bijection for covered maps, or a shortcut between Harer-Zagiers and Jacksons formulas
• A new combinatorial identity for unicellular maps, via a direct bijective approach
• The generating function of ternary trees and continued fractions
• Tesselation and visibility representations of maps on the torus
• Unified bijections for maps with prescribed degrees and girth
• Title not available (Why is that?)
• A bijection for triangulations, quadrangulations, pentagulations, etc.
• Enumeration of edges in some lattices of paths
• Straight-line representations of maps on the torus and other flat surfaces
• Toroidal maps: Schnyder woods, orthogonal surfaces and straight-line representations
• Encoding toroidal triangulations

Cited In (6)

• Blossoming bijection for higher-genus maps
• A bijection for triangulations, quadrangulations, pentagulations, etc.
• Orientations and bijections for toroidal maps with prescribed face-degrees and essential girth
• Transversal structures on triangulations: A combinatorial study and straight-line drawings
• A bijection for essentially 3-connected toroidal maps
• Matching extension in quadrangulations of the torus

This page was built for publication: A bijection for essentially 4-connected toroidal triangulations

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