Finding triangles in a graph: other approaches besides property testing?
For several references for the problem of testing for the existence of a triangle (exactly, not in the property testing framework), see Triangle-free graph on Wikipedia. In particular Alon, Yuster, and Zwick (ESA'94) give an O(m^{1.41}) algorithm, and it can also be done in fast matrix multiplication time which is better for dense graphs.

If you're ok with something in the dynamic graph algorithms setting, I also have one for counting the triangles: 

The h-index of a graph and its application to dynamic subgraph statistics, D. Eppstein and E. S. Spiro, arXiv:0904.3741 and WADS 2009.

In our paper we cite Chiba and Nishizeki (SICOMP 1985) and Itai and Rodeh (SICOMP 1978) for the basic static-algorithm facts that a graph with m edges can have at most O(m^{3/2}) triangles in the worst case and that they can be listed in that amount of time.