Interactions between aircraft, as, e.g., those caused by minimum separation infringements, can trigger non-local cascades of interactions that can propagate over large temporal and spatial scales. Assessing those downstream effects is a computationally complex problem, which has only been tackled over rather limited time horizons. We here propose a methodology to map these interactions into networks, thus representing their potential propagation and the structure induced by them. The result is a conceptually simple and computationally tractable representation, which can be further analyzed using metrics provided by a complex networks theory. We firstly test this methodology using a synthetic airspace, then move on to the analysis of planned and executed trajectories for a large European airspace in the year 2018. We show how these propagation networks reflect the structure of airways, the intervention of air traffic controllers, and how they have evolved through time. We finally discuss potential real-world applications, and some key aspects that need to be further studied to make this a viable instrument in an operational context.