The introduction of a new SESAR scenario in the European Airspace will impact the functioning and the performances of the current Air Traffic Management (ATM) System. The understanding of the features and the limits of the current system could be crucial in order to improve and design the structure of the future ATM. In this paper we present some results of the “Assessment of Critical Delay Patterns and Avalanche Dynamics” PhD project from the ComplexWorld Network. During this project we developed a model of Air Traffic Control (ATC) based on Complex Network theory capable of reproducing the features of the real ATC in three European National Airspaces. We then developed an optimization algorithm based on “Extremal Optimization” in order to build efficient and globally optimized planned trajectories. The ATC model is applied in order to study the efficiency of this new planned trajectories when subject to external perturbations and to compare them to the current situation.