# Flight Level Assignment Using Graph Coloring
## 3 Experimental Evaluation  
### Graphs Used  
For the sake of considering a tractable but sufficiently complex problem, we restricted ourselves to the Spanish airspace. The set of routes for our experiments has been built collecting those routes having both origin and destination in Spain from OpenFlights [31]. The database used as dataset from OpenFlights [31] is composed by 67,663 routes operated by 548 different airlines and between 3321 airports. Among other information, the database includes the source and destination airports, along with their planar coordinates in the map. Among these, we extracted intersecting routes, for which the aim is to ensure different FLs at intersections. The airport locations are considered given by their planar coordinates in the Mercator projection of Spain and the routes are modeled as straight segments from origin to destination, as [PERSON] and Brisset do [2] (Figure 2). The route graph as described will not be used directly as input for the graph coloring described in Section 2.3. Instead, as in [2], we will use an intersection graph \(G=(V,E)\) where each of those airways is a vertex in \(V\) and two vertices are joined by an edge if, and only if, the corresponding routes do intersect (Figure 3). The implementation of the graphs has been done in a Python environment using the _networkX_ library [32]. Figure 3: Intersection graph \(G=(V,E)\) considered, where \(V\) (blue nodes) is the set of routes and the (grey) edges in \(E\) connect two of those routes when they intersect. Figure 2: Airports and intersecting airways on the Mercator projection of Spain. To construct the set \(E\) of edges in such a graph, each pair of routes has to be tested in order to determine whether the routes intersect or not. These intersection tests are performed assuming that the two routes are not bidirectional, because in that case they would certainly intersect. The following two conditions need to be fulfilled by a pair of routes to intersect. First, it is necessary that the convex hull of the four airports (smallest convex set containing them) is a quadrilateral. Otherwise, the convex hull is a triangle and the routes do not intersect (Figure 4). Second, when the convex hull of the four airports is a quadrilateral, the routes intersect if, and only if, the routes represent diagonals of that quadrilateral (Figure 5). In order to distinguish between triangular and quadrilateral convex hulls, we first compute the sign of each triplet, defined as the determinant  
\[\text{sign}(A_{i},A_{j},A_{k})=\left| \begin{array}{ccc}1&1&1\\ A_{i,x}&A_{j,x}&A_{k,x}\\ A_{i,y}&A_{j,y}&A_{k,y}\end{array} \right|, \tag{12}\]  
where \(A_{i,x}\) and \(A_{i,x}\) are, respectively, the horizontal and vertical coordinates of the location for airport \(A_{i}\). That sign equals respectively \(+1\) or \(-1\) when the turn \(A_{i}\), \(A_{j}\), \(A_{k}\) is, respectively, counterclockwise or clockwise. Thus, the outcome of the product \(\text{sign}(A_{1},A_{2},A_{3})\cdot\text{sign}(A_{1},A_{2},A_{4})\cdot\text{ sign}(A_{1},A_{3},A_{4})\cdot\text{sign}(A_{2},A_{3},A_{4})\) is respectively \(+1\) or \(-1\) when the convex hull of the four points is, respectively, a quadrilateral or a triangle. Then, we just check if the routes are diagonals of the quadrilateral (hence crossing) or not. Performing these intersection tests leads to the intersection graph \(G=(V,E)\) depicted in Figure 3, with 6597 edges and 288 vertices. Observe that nodes in this graph correspond to routes in Figure 2.  
Finally, it is interesting to note that each node (route) in the graph does not represent a single flight, but all the flights that take the same route. This means that, in order to compute the fuel consumption for a given FL assignment, the fuel cost for each route is multiplied by the frequency of that route (extracted from the OpenFlights data [31]). We have considered all the flights that take place in a day for internal routes in Spain. Figure 4: Possibilities for the convex hull of the four airports involved in two routes.