On ordering of β-description trees

Huang, Sumin and Kitaev, Sergey (2023) On ordering of β-description trees. Theoretical Computer Science. ISSN 0304-3975 (In Press)

[thumbnail of Huang-Kitaev-TCS-2023-On-ordering-of-beta-description] Text. Filename: Huang_Kitaev_TCS_2023_On_ordering_of_beta_description.pdf
Accepted Author Manuscript
Restricted to Repository staff only until 3 August 2024.
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo
Download (1MB) | Request a copy

Abstract

Tutte introduced planar maps in the 1960s in connection with what later became the celebrated Four-Color Theorem. A planar map is an embedding of a planar graph in the plane. Description trees, in particular, β-description trees, were introduced by Cori, Jacquard and Schaeffer in 1997, and they give a powerful tool to study planar maps. In this paper we introduce a relation on β-description trees and conjecture that this relation is a total order. Towards solving this conjecture, we provide an embedding of β(a, b)-trees into β(a − t, b + t)- trees for t ≤ a ≤ b + t, which is a far-reaching generalisation of an unpublished result of Claesson, Kitaev and Steingrímsson on embedding of β(1, 0)-trees into β(0, 1)-trees that gives a combinatorial proof of the fact that the number of rooted nonseparable planar maps with n + 1 edges is more than the number of bicubic planar maps with 3n edges.

ORCID iDs

Huang, Sumin and Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647;
CORE (COnnecting REpositories)