Kuratowski-type theorems for average genus (Q1204482)

The average genus of a graph \(G\) is the average value of the genus of the imbedding surface, taken over all orientable embeddings of \(G\). In general one expects this number to be large. Calculations reveal it to be close to the maximum genus. In this paper the authors give a list of all cut-edge-free graphs whose average genus is less than or equal to 1. This list consists of a finite number of small graphs, which are given in the paper, and an infinite class of graphs called necklaces (a necklace is a slight variation on a cactus). The authors also give a Kuratowski-type theorem characterizing graphs of maximum genus 1.