  Finding, counting and/or listing triangles (three vertices with three edges)
in large graphs are natural fundamental problems, which received recently much
attention because of their importance in complex network analysis. We provide
here a detailed state of the art on these problems, in a unified way. We note
that, until now, authors paid surprisingly little attention to space
complexity, despite its both fundamental and practical interest. We give the
space complexities of known algorithms and discuss their implications. Then we
propose improvements of a known algorithm, as well as a new algorithm, which
are time optimal for triangle listing and beats previous algorithms concerning
space complexity. They have the additional advantage of performing better on
power-law graphs, which we also study. We finally show with an experimental
study that these two algorithms perform very well in practice, allowing to
handle cases that were previously out of reach.
