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.

In:

J. A. Ellis and I. H. Sudborough and J. S. Turner,

Information and Computation, vol. 113, pp. 50--79, (1994),

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:

Proceedings of the 8th Annual European Symposium on Algorithms, pp. 403--414, (2000).

A reformulation of this method can also be found in:

J. Ellis and M. Markov, Information and Computation, Volume 192, Issue 2, pp. 123-161, 2004.