**Arboricity and bipartite subgraph listing algorithms**.

D. Eppstein.

Tech. Rep. 94-11, ICS, UCI, 1994.

*Inf. Proc. Lett.*51: 207–211, 1994.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).

Nowadays 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.

**Dynamic connectivity in digital images**.

D. Eppstein.

Tech. Rep. 96-13, ICS, UCI, 1996.

*Inf. Proc. Lett.*62: 121–126, 1997.Any algorithm that maintains the connected components of a bitmap image must take Omega(log

*n*/ log log*n*) time per change to the image. The problem can be solved in O(log*n*) time per change using dynamic planar graph techniques. We discuss applications to computer Go and other games.

Journals – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.