Counting non-isomorphic chord diagrams. (English) Zbl 0913.68148

Cori, Robert; Marcus, Michel

Theor. Comput. Sci. 204, No. 1-2, 55-73 (1998).

Summary: Different formulas counting families of non-isomorphic chord diagrams are given: planar and toroidal ones and those of maximal genus. These formulas are obtained establishing results on the structure of the automorphism group of diagrams of a given genus.

MSC:

68R10

Graph theory (including graph drawing) in computer science

Keywords:

enumeration; isomorphic structures; maps; chords

References:

[1]	Bar-Natan, D., On the Vassiliev node invaraints, Topology, 34, 423-472, (1995) · Zbl 0898.57001
[2]	Bessis, L., Harvey-wiman hypermaps, () · Zbl 0878.30030
[3]	Bétréma, J.; Cori, R.; Sossinsky, A., Diagrammes de cordes et courbes de Gauss, (1994), Université Bordeauxl, Unpublished manuscript
[4]	Bianchi, G.; Cori, R., Colorings of hypermaps and a conjecture of Brenner and Lyndon, Pacific J. math., 110, 41-48, (1984) · Zbl 0531.05034
[5]	Cori, R., Un code pour LES graphes planaires et ses applicationse, Astérisque, 27, (1975) · Zbl 0313.05115
[6]	Cori, R.; Machi, A., Maps, hypermaps and their automorphisms: a survey, I, II, III, Expo. math., 10, 403-467, (1992) · Zbl 0772.05039
[7]	Harer, J.; Zagier, D., The Euler characteristic of the moduli space of curves, Invent. math., 85, 457-485, (1986) · Zbl 0616.14017
[8]	Jackson, D.M., Counting cycles in permutations by group characters with an application to a topological problem, Trans. amer. math. soc., 299, 785-801, (1987) · Zbl 0655.05005
[9]	Labelle, G.; Leroux, P., Enumeration of plane trees according to their degrees distribution, Discrete math., 157, 227-240, (1996) · Zbl 0868.05030
[10]	Liskovets, V.A., Enumeration of non-isomorphic planar maps, Selecta math. soviet., 4, 4, 303-323, (1985) · Zbl 0578.05033
[11]	Machi, A., The Riemann-Hurwitz formula for the centralizer of a pair of permutations, Arch. der math., 42, 280-288, (1984) · Zbl 0522.20003
[12]	Tutte, W.T., A census of planar maps, Canad. J. math., 15, 249-271, (1963) · Zbl 0115.17305
[13]	Walkup, D.W., The number of plane trees, Mathematika, 19, 200-204, (1972) · Zbl 0253.05106
[14]	Walsh, T.R.S.; Lehman, A.B.; Walsh, T.R.S.; Lehman, A.B., Counting rooted maps by genus I, II, J. combin. theory (B), J. combin. theory (B), 13, 122-141, (1972) · Zbl 0228.05108
[15]	Walsh, T.R.S.; Lehman, A.B., Counting rooted maps by genus III, J. combin. theory (B), 18, 200-204, (1975) · Zbl 0299.05110