Any way to find a 3-vertex cycle in a graph using an incidence matrix in O(nm) time?
Let's assume first that your graph is connected, so that $m \geq n-1$. Convert your incidence matrix into an adjacency matrix in time $O(n^2) = O(nm)$. Now go over all $m$ edges, and for each edge $(i,j)$, go over all vertices $k$ and check in $O(1)$ whether $i,j,k$ is a triangle in the graph (using the adjacency matrix), for an overall running time of $O(nm)$.

If your graph is not connected, then use DFS/BFS to find its connected components, and run the procedure above on each of them. Assuming that the $i$th connected component consists of $n_i$ vertices and $m_i$ edges, the running time is $O(\sum_i n_i m_i) \leq O(\sum_{ij} n_i m_j) = O(nm)$.