Jump number maximization for proper interval graphs and series-parallel graphs (Q1818782)

The author considers the graph-theoretic equivalent to the concept of a jump in linear extensions of partially ordered sets. Given a graph \(G(V,E)\) and a linear ordering of the vertices of \(G\), a jump of this linear ordering is a non-adjacent pair of vertices that appear consecutively in the linear ordering. As in order theory, one can consider optimization problems like finding a linear ordering with the minimal/maximal number of jumps. Since a graph has a Hamiltonian path if and only if there is a linear ordering of the vertices without a jump, it follows that both the minimization and the maximization problem are NP-hard. The author both lists known results and observes some new results on the complexity of the jump number minimization/maximization problem for a variety of graph classes including trees, series-parallel, chordal, split, comparability, bipartite, permutation, circular arc, proper circular arc, interval, proper interval, planar, circle, and edge graphs. In particular he gives an \(O(|V|\log |V|)\) time algorithm for the jump maximization problem on proper interval graphs, and an \(O(|E||V|)\) time algorithm for the same problem on series-parallel graphs.