Séminaire Lotharingien de Combinatoire, B54Al (2007), 44 pp.

Éric Fusy

Counting Unrooted Maps Using Tree-Decomposition

Abstract. We present a new method to count unrooted maps on the sphere up to orientation-preserving homeomorphisms. The principle, called tree-decomposition, is to deform a map into an arborescent structure whose nodes are occupied by constrained maps. Tree-decomposition turns out to be very efficient and flexible for the enumeration of constrained families of maps. In this article, the method is applied to count unrooted 2-connected maps and, more importantly, to count unrooted 3-connected maps, which correspond to the combinatorial types of oriented convex polyhedra. Our method improves significantly on the previously best-known complexity to enumerate unrooted 3-connected maps.

Received: December 20, 2005. Accepted: December 29, 2006. Final Version: January 24, 2007.

The following versions are available: