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.
  • $\begingroup$ 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? $\endgroup$
    – M.Monet
    Jul 3, 2019 at 21:55
  • $\begingroup$ Is the graph sparse or dense? (Or can be any?) $\endgroup$ Jul 4, 2019 at 8:32
  • $\begingroup$ @CyriacAntony It can be any as you suggest. $\endgroup$
    – user15587
    Jul 4, 2019 at 18:46


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.