Counting Subgraphs in Relational Event Graphs
Farah Chanchary

Subgraph listing is a fundamental operation to many graph and network analyses. Chiba and Nishizeki introduced a simple edge-searching strategy in 1985 to list certain kinds of subgraphs including triangles, quadrangles, complete subgraphs of a fixed order and cliques, in $$O(a(G)m)$$ time, where $$a(G)$$ is the arboricity of the graph $$G$$.

We consider applying this technique to develop data structures which support queries to determine the number of subgraphs in a relational event graph with query windows chosen dynamically rather than a priori.