1. Construct list of pairs of vertices incident on crossings by examining neighborhood of each crossing vertex.
2. To perform the clockwise traversal of crossings for every pair as shown in the previous section, the crossings for every pair must be inserted in the list in clockwise order. We can traverse the neighborhood of each vertex and place crossings in the corresponding list, since the neighborhood of each vertex is in clockwise order from input, this can be done easily.

Performing this traversal costs O(n) time. There are a linear number of crossings, and the traversal of each neighborhood takes time proportional to the degree of each vertex and linear for every vertex in the graph.