Quantifying the link between aircraft interaction complexity and the decision making process of air traffic controllers can help developing sound cognitive models and effective intelligent supportive tools. In this paper, we introduced a new relational complexity network framework derived from network theory and cognitive mechanisms to explain some key aspects in the decisional processes of air traffic control tasks. In the validating experiment, we manipulated different aircraft interaction patterns and found that controllers' workload ranking, conflict detection rate, intervention decision and task completion time were significantly influenced by positions of single aircraft or aircraft pairs in the relational complexity network. Theoretical and practical contributions are discussed.