The h-Index of a Graph and its Application to Dynamic Subgraph Statistics

David Eppstein, Emma S. Spiro

We describe a data structure that maintains the number of triangles in a dynamic undirected graph, subject to insertions and deletions of edges and of degree-zero vertices. More ge…