Some Problems on Doubly Periodic Infinite Graphs

Abstract:

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.