Counting unrooted maps using tree-decomposition

MaRDI QIDQ2654585zbMATH OpenFDO

Authors Éric Fusy

Publication date 19 January 2010

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

Full work available at URL https://arxiv.org/abs/math/0601123, https://eudml.org/doc/224333, http://www.emis.de/journals/SLC/wpapers/s54Afusy.html

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

Mathematics Subject Classification ID

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

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.

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

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)