Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

We show that finding weak components, finding an Eulerian path, and testing 2-colorability of two-dimensional doubly periodic graphs can be done in polynomial time with respect to the size of the static graph.