How to find the largest connected component of an undirected graph using its incidence matrix?

Question

Usually, finding the largest connected component of a graph requires a DFS/BFS over all vertices to find the components, and then selecting the largest one found.

Suppose I only have an incidence matrix as a representation of a graph. Is there another algorithm (faster perhaps) to find the largest component by taking advantage of the structure of the incidence matrix?

Answer 1

There could be an algorithm that would be useful for a sparse graph that takes $O(|E|)$ time. In that case you would want to just have a list of edges and would not want to have to scan an adjacency matrix. This would be the fastest possible in order to be certain you've found all components.

Answer 2

From the incidence matrix, you can obtain the Laplacian matrix, then from there, you know that the null space of the Laplacian gives you the connected components of your graph.