Map genus, forbidden maps, and monadic second-order logic (Q1856334)

Graphs can be described in terms of a binary edge-relation, and so can be expressed as a logical formula. These formulas cannot express some basic graph-theoretic properties in first-order logic. Second-order logic allows new variables denoting relations and are subject to quantification, and many graph-theoretic properties can be expressed in second-order logic. Monadic second-order logic lies between first- and second-order logic; it allows set variables but no variables denoting binary relations or relations of larger arity. A map is a graph together with, for each vertex, a cyclic permutation of the edges incident with that vertex. Maps describe embeddings of the graph into oriented surfaces; these surfaces are characterized in terms of a non-negative integer called their genus. Maps that embed on a surface of genus at most \(g\) are characterized in terms of a finite number of forbidden submaps. This characterization gives the existence of the embedding, but does not specify the particular embedding. In this paper the authors give a different characterization of graphs that, in addition to stating its existence, specifies the relevant surface embedding. This characterization is expressible in monadic second-order logic.