@JamesPropp Do you have a strong reason to believe that it is even possible to compute the Tutte polynomial with current capabilities for $n=16$? My understanding is that algorithmically it is a very difficult problem (hard to approximate for planar graphs) and all current algorithms are extremely slow (worse than exponential I think) - which would make the runtime blow up even for small $n$.

What is a directed random regular graph? How are you using randomness to assign directions to edges of a $d$ regular graph? For instance, just randomly assigning $d_{in}$ out of the $d$ incident edges to be inward will not work as it may create conflicts.

@JukkaKohonen yes

@PeterTaylor The second interpretation. I mean it in the sense that for a graph family where there is a graph $G_n$ on $n$ vertices for every $n \in \mathbb{N}$, there is a polynomially $f(n)$ such that the number of cycles in $G_n$ is bounded by $f(n)$. This is true for trees for instance, but false for planar graphs.

@darijgrinberg yes