A gain graph is a triple (G,h,H) where G is a graph, H is a group, and h is a homomorphism from the free group on the edges of G to H. Gain graphs appear in physics, rigidity theory, geometry of polytopes, graph theory, operations research, etc. An ordered cycle in G is called balanced if it lies in the kernel of h. A gain graph is called balanced if all its cycles are balanced. For some choices of H, I will give necessary and sufficient conditions for a gain graph (G,h,H) to be balanced. For example, if H is free abelian, then (G,h,H) is balanced if and only if all elements of an arbitrary basis of its binary cycle space are balanced. This is also true for any H such that its abelianization is infinite and torsion-free. However, if the abelianization of H is finite, our criterion does not work.
The case of torsion-free abelian H is important to polyhedral geometry and physics. I will describe applications of our criterion to recognizing if a given polyhedral partition of a domain in n-space can be lifted to a convex surface. If time permits, I'll describe applications to computing the dimension of the space of Crr-1-splines over a cell-decomposition of a domain D in n-space with H1(D)=0.
This is a joint ongoing work with Tom Zaslavsky.