  We consider the problem of analyzing social network data sets in which the
edges of the network have timestamps, and we wish to analyze the subgraphs
formed from edges in contiguous subintervals of these timestamps. We provide
data structures for these problems that use near-linear preprocessing time,
linear space, and sublogarithmic query time to handle queries that ask for the
number of connected components, number of components that contain cycles,
number of vertices whose degree equals or is at most some predetermined value,
number of vertices that can be reached from a starting set of vertices by
time-increasing paths, and related queries.
