Coding Properties of Breadth-First Search Orderings

Though it is known for long that there is as many pointed maps with m edges as connected involutions on {1,…, 2m + 2}, no actual bijection were known between these combinatorial objects. Such a bijection is described here as two reciprocal constructions: a map encoding and a map construction. These constructions appear to be simply derived from the properties of breadth-first search orderings.