Non-recursive Counts of Graphs on Surfaces

The problem of map enumeration concerns counting connected spatial graphs, with a specified number j of vertices, that can be embedded in a compact surface of genus g in such a way that its complement yields a cellular decomposition of the surface. As such this problem lies at the cross-roads of combinatorial studies in low dimensional topology and graph theory. The determination of explicit formulae for map counts, in terms of closed classical combinatorial functions of g and j as opposed to a recursive prescription, has been a long-standing problem with explicit results known only for very low values of g. In this paper, we derive closed-form expressions for counts of maps with an arbitrary number of even-valent vertices, embedded in surfaces of arbitrary genus. In particular, we exhibit a number of higher genus examples for 4-valent maps that have not appeared prior in the literature.