# A dynamic data structure to list triangles

Consider an undirected graph with $$n$$ nodes. Is there an efficient data structure that supports the following operations?

• Insert an edge into the graph
• Delete an edge from the graph
• Given a query edge $$(i,j)$$, list all the triangles that include that edge. There can be $$n$$ of these in the worst case but ideally this operation would be sublinear if the number of triangles to be reported is.
• I haven't looked at it very closely, but maybe the techniques in this paper arxiv.org/abs/1804.02780 can be used for your kind of queries? Jul 3, 2019 at 21:55
• Is the graph sparse or dense? (Or can be any?) Jul 4, 2019 at 8:32
• @CyriacAntony It can be any as you suggest.
– user15587
Jul 4, 2019 at 18:46