Pathwidth, node search number and vertex separation are different ways of defining the same notion. Path decompositions and search strategies can be derived from linear layouts. Computing this parameter is, in general, an NP-complete problem and remains NP-complete even for planar graphs of maximum degree three.
we showed how to compute the vertex separation of trees in linear time. That paper suggested an algorithm for the computation of optimal layouts in time O(n log n).
It was not until later that a way of computing the layouts themselves in linear time was described in:
A reformulation of this method can also be found in: