Is there a method for systematically enumerating sets of collinear nodes in a graph? This question arises directly from the discussion in this MSE question which I'd posted a few days back: Counting the number of polygons in a figure. In that question, I'm currently trying to find a method to enumerate the number of triangles in any general graph. The algorithm so far is to compute $\text{Tr}(A^3)/3!$, where $A$ is the adjacency matrix of the graph. This gives the number of triangles, including the degenerate triangles arising out of triplet sets of collinear nodes. So, for obtaining the actual number of triangles, one needs to subtract the number of such degenerate triangles, which leads to my question: Is there a method for systematically enumerating triplet sets of collinear nodes in a graph?
 A: The solution may depend on how the graph has been specified. The general approach I can think of relies on first identifying all lines containing 3 or more nodes.
If a line contains $m$ nodes, it will contain $\binom{m}{3}$ degenerate triangles. Thus, if the entire graph contains $k$ lines with $m_1,\ldots,m_k\ge3$ nodes in each of them, the total number of degenerate triangles is $\sum_{i=1}^k \binom{m_i}{3}$.
The total number of non-degenerate lines will then be
$\frac{Tr(A^3)}{3}-\sum_{i=1}^k \binom{m_i}{3}$.
A: I think the fastest way to calculate this is to check, for each triangle, wheter or not the nodes are collinear, because the number of possible lines is the number of edges of the graph, and I assume the number of triangles will be far less.
If you really want to enumerate the collinear nodes, you could sort them by their coordinates and just check all triples that may be collinear. (Some can't be, because you sorted them.)
A: Construct a new graph $H$ whose vertices are the edges of the original graph. The edges in the new new graph are the pairs of edges in the older graph that determine the same line(they fall on the same line). Then, compute the number of triangles in the new graph using the formula.   
