Counting unrooted maps using tree-decomposition

zbMATH Open1207.05089arXivmath/0601123MaRDI QIDQ2654585FDOQ2654585

Authors: Éric Fusy 

Publication date: 19 January 2010

Published in: Séminaire Lotharingien de Combinatoire (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/math/0601123

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Counting unrooted maps on the plane
• scientific article; zbMATH DE number 3871396
• Counting unrooted loopless planar maps
• Enumeration of unrooted orientable maps of arbitrary genus by number of edges and vertices
• Efficient enumeration of sensed planar maps

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Enumeration in graph theory (05C30)

Cited In (3)

• Counting unlabeled structures
• Symmetries of unlabelled planar triangulations
• Counting unlabeled \(k\)-trees

This page was built for publication: Counting unrooted maps using tree-decomposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2654585)