The design of efficient graph algorithms continues to be one of the central problems of computer science. Graphs can be used to model everything from social networks to biological systems to boolean circuits. There are currently many approaches to the design of graph algorithms, but there still remain many open problems. The proposed research studies a new algebraic approach to the design of efficient graph algorithms that is based on the Jacobian of a graph. Every graph has an abelian group?the Jacobian? that is associated with it. This group is the same for isomorphic graphs, although it does not uniquely determine the graph. However, the Jacobian does contain a great deal of important information about the graph. The plan is to exploit the Jacobian to design new efficient algorithms for important graph problems. Some of the problems that will be studied include: sampling random sub-graphs with specific properties, graph isomorphism for new classes of graphs, and many other problems. The success of the proposed research will significantly increase our understanding of graph algorithms. It will not only discover new algorithms, but will open the door on an entirely new approach to the creation of additional algorithms.
