The largest demigenus of a bipartite signed graph (Q5937463)

A signed graph is a graph with signed edges. A signed graph \(G\) is orientation embedded in a closed surface \(S\) when it is embedded so that a cycle of \(G\) is orientation preserving on \(S\) precisely when the product of signs on the cycle is positive. The demigenus of signed graph \(G\) is the smallest demigenus of a closed surface (that is, the number of crosscaps plus twice the number of handles) upon which \(G\) can be orientation embedded. In the paper it is shown that for a signed bipartite graph with partite sets of size \(r\) and \(s\) the largest possible demigenus is \((r-1)(s-1)+1\). An equivalent sign-free restatement of the result is that the complete bipartite graph \(K_{2r,2s}\) admits a minimum genus orientable embedding which is antipodal---one which admits an orientation-reversing involutory self-homeomorphism. A few additional related topics are discussed, including signed minors and signed maximum genus.