Orientation embedding of signed graphs

A signed graph Σ consists of a graph and a sign labeling of its edges. A polygon in Σ is “balanced” if its sign product is positiive. A signed graph is “orientatio embedded” in a surface if it is topologically embedded and a polygon is balanced precisely when traveling once around it preserves orientation. We explore the extension to orientation embedding of the ordinary theory of graph embedding. Let d(Σ) be the demigenus (= 2 - x(S)) of the unique smallest surface S in which Σ has an orientation embedding. Our main results are an easy one, that if Σ has connected components Σ₁, Σ2], ?, then d(Σ) = d(Σ₁) + ?, and a hard one, that if Σ has a cut vertex v that splits Σ into Σ₁, Σ₂, ?, then d(Σ) = d(Σ₁) + d(Σ₂) + ? -δ, where δ depends on the number of Σ_i in which v is “loopable”, that is, in which d(Σ_i) = d(Σ_{i with a negative loop added to v}). This is as with ordinary orientable grpah embedidng except for the existence of the term δ in the cut-vertex formula. Since loopability is crucial, we give some partial criteria for it. (A complete characterization seems difficult.) We conclude with an application to forbidden subgraphs and minors for orientation embeddability in a given surface. © 1929 John Wiley & Sons, Inc.