The D’Esopo-Pape algorithm is exponential in the worst case. Consider the following method to construct pathological graphs of n vertices (Kershenbaum 1981), each vertex identified by a number 1, . ....

The D’Esopo-Pape algorithm is exponential in the worst case. Consider the following method to construct pathological graphs of n vertices (Kershenbaum 1981), each vertex identified by a number 1, . . . , n:

The vertices adjacent to vertex 1 are put in ascending order and the remaining adjacency lists are in descending order. Using this algorithm, construct a five-vertex graph and execute the D’Esopo-Pape algorithm showing all changes in the deque and all edge updates. What generalization can you make about applying Pape’s method to such graphs?