Algorithm for checking if a cubic graph has a triangle If we have a graph $G$ with $n$ vertices and $m$ edges, then in general, the problem of listing all triangles in $G$ is solvable in $O(m\sqrt{m})$ time [1]. If we consider only the planar graphs, then the same problem can be solved in $O(n)$ time [2]. I am interested in the similar problem for cubic graphs (3-regular graphs) or for graphs with maximum degree at most 3. For me, answer for the most basic question will suffice: is there an efficient algorithm for determining if given graph of maximum degree 3 contains a triangle?
EDIT: When I say "efficient algorithm" I mean running time $O(n\log^cn)$, for some constant $c \geq 1$.
[1] Alon, N., Yuster, R., Zwick, U. (1997), Finding and counting given length cycles, Algorithmica, 17(3), pp. 209–223.
[2] Papadimitriou, C., Yannakakis, M. (1981), The clique problem for planar graphs, Inform.
Proc. Letters 13, pp. 131–133.
 A: In any graph, we can also loop through all the vertices, and for every vertex $v$, check if any of $v$'s neighbors are adjacent to each other. This is at worst an $O(n \cdot \Delta(G)^2)$ algorithm, where $\Delta(G)$ is the maximum degree of $G$.
It's easier to explain, but not as good as the algorithm in the first paper you cite which runs in $O(n \cdot d(G))$, time, where $d(G)$ is the degeneracy of the graph: the smallest value of $k$ such that every subgraph has a vertex of degree at most $k$.
But in the case of cubic graphs, both $\Delta(G)$ and $d(G)$ are constant, and so even the simple algorithm runs in $O(n)$ time.
A: If the maximum degree of the graph $G = (V, E)$ is at most $3$, then the problem of listing all triangles in the graph can be solved in $O(n)$ time. The algorithm is quite simple.

  
*
  
*for each edge $e = (u, v)$ in $G$:
  
*$\ \ $let $\ell_u$ ($\ell_v$) be the adjacent list of $u$ ($v$) such that the vertices are ordered in the list;
  
*$\ \ $find all $w \in \ell_u \cap \ell_v$ using $O(|\ell_u| + |\ell_v|)$ time and output the corresponding triangles;
  

The complexity of this algorithm is $O(\sum_{(u, v) \in E}(\delta(u) + \delta(v)) = O(|E|) = O(n)$ because $\delta(u), \delta(v) \leq 3$ and $|E| = O(n)$.
