Map genus, forbidden maps, and monadic second-order logic
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.
- The monadic second-order logic of graphs. XII: Planar graphs and planar maps
- A characterization of the embeddability of graphs on the surface of given genus
- The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
- On zero-one and convergence laws for graphs embeddable on a fixed surface
- scientific article; zbMATH DE number 1059243
This page was built for publication: Map genus, forbidden maps, and monadic second-order logic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1856334)
