A few words about maps

In this paper, we survey some properties, encoding, and bijections involving combinatorial maps, double occurrence words, and chord diagrams. We particularly study quasi-trees from a purely combinatorial point of view and derive a topological representation of maps with a given spanning quasi-tree u...

Full description

Saved in:
Bibliographic Details
Published in:European journal of combinatorics 2024-06, Vol.119, p.103810, Article 103810
Main Authors: Cori, Robert, Jiang, Yiting, Ossona de Mendez, Patrice, Rosenstiehl, Pierre
Format: Article
Language:English
Subjects:
Computer Science
Mathematics
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we survey some properties, encoding, and bijections involving combinatorial maps, double occurrence words, and chord diagrams. We particularly study quasi-trees from a purely combinatorial point of view and derive a topological representation of maps with a given spanning quasi-tree using two fundamental polygons, which extends the representation of planar maps based on the equivalence with bipartite circle graphs. Then, we focus on Depth-First Search trees and their connection with a poset we define on the spanning quasi-trees of a map. We apply the bijections obtained in the first section to the problem of enumerating loopless rooted maps. Finally, we return to the planar case and discuss a decomposition of planar rooted loopless maps and its consequences on planar rooted loopless map enumeration.
ISSN:0195-6698
1095-9971
DOI:10.1016/j.ejc.2023.103810