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:
We reformulate this method and show how to compute the vertex separation of unicylic graphs in:
This algorithm runs in time O(n log n), but it seems that adding one edge to a tree necessitates a considerably more elaborate algorithm.