What is the relationship between the NOx and the excess air?

In combustion we consider 3 NOx sources: Thermal NOx, Fuel NOx and Prompt NOx. The concentration of thermal NOx is progressive with the combustion temperature. Mostly in fired heaters NOx formation is Thermal/fuel NOx formation. As we try to maintain the temperature Excess air will form more NOx. 

"High temperature/more excess air leads to NOx formation." 

So the relationship is that NOx formation is related to temperature which will lead to thermal dissociation of N2 and finally react with O2 molecules at high temperature to form NOx.

Formation of thermal NOx is progressive with the peak flame temperature, so higher temperature means higher thermal NOx. 

However reducing oxygen concentration in the (primary) combustion zone reduces as well thermal as fuel NOx formations), also depending of the fuel used, and it is one of the commonly practiced NOx reducing techniques. (It is easy since you don't have to modify your equipment). So indeed, increasing excess air ratio will, although degressively increase converted NOx especially in the primary combustion zone. Fuel staging or air staging may be one of the answers to reduce the NOx content emission with the flue gas.

So increasing the combustion temperature means increasing formation of thermal NOx and the other way around. So increasing excess air means reducing flame temperature means reduction of NOx progressively. Fuel NOx speaks for itself and prompt NOx is formed in fuel rich layers in the combustion.