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.