Arboricity and bipartite subgraph listing algorithms.
D. Eppstein.
Tech. Rep. 94-11, ICS, UCI, 1994.
Inf. Proc. Lett. 51: 207–211, 1994, doi:10.1016/0020-0190(94)90121-X.
For any sparse family of graphs, one can list in linear time all complete bipartite subgraphs of a graph in the family. There are \(O(n)\) complete bipartite subgraphs of a graph in the family, and the sum of the numbers of vertices in these subgraphs is also \(O(n)\).
These results can also be interpreted as a form of formal concept analysis. If a set of objects and attributes is sparse (e.g., if it is generated by adding objects and attributes one at a time, where each newly-added object is given \(O(1)\) attributes and each newly-added attribute is held by \(O(1)\) objects) then the total size of all concepts in its concept lattice is linear, and this lattice may be generated in linear time.