We can use the Euler characteristic of the surface, mainly ~V-E+F = 2-2g~ where ~g~ is the number of holes. Now we have to count ~V~, ~E~, and ~F~. To count ~F~, we can simply do a DFS on the faces, marking each face we visit. The number of visited nodes is exactly ~F~. Because each face has degree exactly ~4~, by the handshaking lemma ~E = 2F~.

The trickiest part is counting the vertices. For each face, you can calculate the degrees of the four vertices forming the side. Let's say you are trying to calculate the degree of the left vertex of the edge you are pointing at. You can mark the current face and start a "left cycle" until you return to the marked face. The number of faces you visit is exactly the degree of the vertex, you can easily see this by "flattening" out the part around that vertex, it essentially looks like a flower with either ~3~, ~4~, or ~5~ petals. Now you can easily infer the total number of vertices and then the total number of holes!