How should I approach the problem of predicting or calculating the change in the number of triangles when a new edge is added under these constraints? Are there specific combinatorial methods or matrix operations that would be particularly useful?
The way I am adding edges is by adding new lines to the graph that do not intersect current edges and are not parallel with any current lines. I am thinking of using adjacency matrix and raise it to power of three to get the trace, but I don't know how to systematically vary the adjacency matrix to mimic my way of adding new lines.
Any help would be appreciated!
For all $n \ge 5$, there are multiple configurations of this type, and they produce different numbers of triangles. For example, here is a different $5$-line arrangement with only $3$ triangles, rather than $5$:
A decent amount of research has been done into finding the largest possible number of triangles. For example, Füredi and Palásti (Arrangements of lines with a large number of triangles, 1984) prove that there are $n$-line arrangements with as many as $\frac13 n(n-3)$ triangles.
I couldn't find citations for minimizing the number of triangles. (I think the issue is that if we allow parallel lines, then the lower bound is $0$, so the question has to be stated more carefully, and has attracted less interest as a result.) Here's an idea for an $O(n \log n)$ construction.
Take two arrangements of $n/2$ lines (recursively constructed in the same way). Rotate them, if necessary, so that there are no perfectly vertical or horizontal lines. For the first one, stretch it by a very large amount horizontally, so that all its lines have very shallow slopes. For the second one, stretch it by a very large amount vertically, so that all of its lines have very steep slopes. Now lay them on top of each other so that the intersections between the two groups of $n/2$ lines are very far away from old intersections.
The result is that the $n/2$ lines from one set intersect the $n/2$ lines from the other set in an approximation of a rectangular grid, creating no triangles. There is, however, a danger of creating up to new $n$ triangles in a different way. Each group of $n/2$ lines created $n$ unbounded regions (for $2n$ total), and half of those turn into bounded regions when they meet the approximate rectangular grid - bounded regions which could be triangles. Also, of course, we keep the triangles in both of the $n/2$-line arrangements.
If $f(n)$ is the number of triangles obtained from $n$ lines constructed in this way, then we have $f(n) \le 2 f(n/2) + n$, with $f(2)=0$. This gives us $f(n) \le n \log_2 n$ as an upper bound.
I bet that arrangements with only $O(n)$ triangles are possible, and maybe even this construction can be shown to have only $O(n)$ triangles with a more careful analysis. (We basically assume that when unbounded regions turn into bounded ones, they all make triangles in the worst case, but I think we can avoid that.)