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: