Using graph concepts to assess the feasibility a sequenced air traffic flow with low conflict rate

International audienceIn this paper, we propose to study feasibility issues of a new air traffic paradigm. In this paradigm, aircraft are following immaterial moving points in such a way that the traffic density is maximized and no conflict (or at most very few) occurs between aircraft. We provide lower and upper bounds on the maximum density of a solution. In particular, we characterize the density of the solution according to the colorability of an auxiliary graph, modelling the potential conflicts between moving points