An obstruction to embedding graphs in surfaces (Q1262320)

It is well known that there is a one-to-one correspondence between imbedding schemes (P,\(\lambda)\) for a fixed connected graph G and 2-cell imbeddings of G into closed 2-manifolds S (S is orientable if and only if each cycle of G has an even number of edges e with \(\lambda (e)=1).\) Now let T be a spanning tree for G, with \(\lambda (e)=0\) for each \(e\in E(T).\) Two edges \(e_ 1,e_ 2\in E(G)-E(T)\) are said to overlap if either \(e_ 1=e_ 2\) and \(\lambda (e_ 1)=1\) or \(e_ 1\neq e_ 2\) and the imbedding of \(T+e_ 1+e_ 2\) induced by \((P,\lambda^ 1)\) is non- planar, where \(\lambda^ 1(e)=0\) for all \(e\in E(G)\). The overlap matrix A has rows and columns indexed by edges in \(G-E(T)\) and ef-entry \(A_{ef}=f\) if e and f overlap; \(A_{ef}=0\) otherwise. The following theorem is proven. Let (P,\(\lambda)\) describe a 2-cell imbedding of a connected graph G on a closed 2-manifold S. Let T be a spanning tree of G, with \(\lambda (e)=0\) for each \(e\in E(T).\) Let A be the corresponding overlap matrix, with rank A the rank of A over GF(2). Then: (1) If S is orientable, the genus of the imbedding is \(\gamma (S)=1/2\quad rank A.\) (2) If S is nonorientable, the nonorientable genus of the imbedding is \({\tilde \gamma}(S)=rank A.\) Application of this theorem is made, both to provide new proofs of several classical results in topological graph theory and also as a new method to obtain lower bounds on the two genus parameters (orientable and nonorientable) for graphs.